COMP30026 Models of Computation - Assignment 2: Regular Languages, DFA Construction, Context-Free Languages, Closure Properties and Pumping Lemma
Aims
Assignment 2
COMP30026 Models of Computation School of Computing and Information Systems
To improve your understanding of formal languages, automata, and grammars;
to develop your skills in analysis and formal reasoning about complex concepts,
and to practise writing down formal arguments with clarity.
Marking
Each question is worth 2 marks, for a total of 12. We aim to ensure that anyone with a basic comprehension of the subject matter receives a passing mark. Getting full marks is intended to be considerably more difficult; the harder questions provide an opportunity for students to distinguish themselves.
Your answers will be marked on correctness and clarity. Do not leave us guessing! We are trying to give you feedback, so you can improve. It is better to be clear and wrong; vague answers will attract few if any marks. This also means you must show your working in mechanical questions!
Finally, make sure your writing is legible! We cannot mark what we cannot read. (Keep in mind that the exam will be on paper, so this will be even more important later!)
Academic Integrity
In this assignment, individual work is called for. By submitting work for assessment you declare that:
-
You understand the University’s policy on academic integrity.
-
The work submitted is your original work.
-
You have not been unduly assisted by any other person or third party.
-
You have not unduly assisted anyone else.
-
You have not used any unauthorized materials, including but not limited to AI and translation software
However, if you get stuck, you can use the discussion board to ask any ques- tions you have. If your question reveals anything about your approach or work- ing, please make sure that it is set to “private”.
You may only discuss the assignment in basic terms with your peers (e.g. clarifying what the question is asking, or recommending useful exercises). You may not directly help others in solving these problems, even by suggesting strategies.
Soliciting or accepting further help from non-staff is cheating and will lead to disciplinary action.
Submission – VERY IMPORTANT!
Submission is via Gradescope. Q4–Q6 are written questions and will be sub- mitted as usual. But for Q1–Q3, you will submit your answers as Python programs. For submission, you will make use of the Python automata library, available at https://pypi.org/project/automata-lib/. To use the visual component (highly recommended), you must first install PyGraphviz by fol- lowing the instructions at https://pygraphviz.github.io/documentation/ stable/install.html.
We highly recommend installing the visual component, so you can visualize your automata before submission. If you do so, the library supports rendering automata automatically in Jupyter notebooks, which we strongly recommend. In any case, it will be easiest for you to start on paper and then transfer your work!
When you submit, the autograder will run some sanity checks to make sure your code is well-formed and passes very basic testing. More thorough testing will be conducted later.
Submitted code will only be assessed for correctness. Other at- tributes, such as readability or efficiency, will not be assessed. (Nonetheless, your code should finish almost instantaneously. If it is taking a noticeable amount of time, that is a sign that something is wrong.)
Q1 Regular Languages: Zero Blocks
Consider the language 𝐿 of all binary strings with at least two blocks of 0’s of even length, where we define a “block of 0’s” to be a maximal nonempty substring of 0’s. (By maximal, we mean that a block of 0’s is not adjacent to any other 0’s.) For example:
-
The string 0000100 has two blocks of 0’s of even length and is in 𝐿.
-
The string 000 has only one block of 0’s and is not in 𝐿.
-
The string 00100100001000111 has three blocks of 0’s of even length, so it is in 𝐿. The odd-length block of zeros is irrelevant.
For submission, upload a single Python source file q1.py which defines func- tions q1a() and q1b().
• The function q1a() takes no arguments and must return an instance of automata.fa.dfa.DFA.
• The function q1b() takes no arguments and must return a string. The string is a regular expression following the syntax at https://caleb531. github.io/automata/api/regular-expressions/. Their syntax offers extra operators, but use only union (|), star (*), concatenation (juxtapo- sition), and grouping (( and )) in your submission. (The format will be checked will be automatically checked at submission time.)
Task A
Write a function q1a() which returns a DFA that recognises 𝐿. Task B
Write a function q1b() which returns a regular expression for 𝐿.
Q2 DFA Construction: Injection
Given languages 𝐿𝐴 and 𝐿𝐵 over an alphabet Σ, define inject(𝐿𝐴,𝐿𝐵) to be the language
{𝑥𝑤𝑦 ∣ 𝑥𝑦 ∈ 𝐿𝐴,𝑤 ∈ 𝐿𝐵}.
That is, the language inject(𝐿𝐴,𝐿𝐵) is the set of all strings which can be made by inserting, at any point, a string from 𝐿𝐵 into a string from 𝐿𝐴.1
If 𝐿𝐴 and 𝐿𝐵 are regular, then inject(𝐿𝐴,𝐿𝐵) is also regular. The goal of this question is to design a construction method that, given DFAs 𝐴 for 𝐿𝐴 and 𝐵 for 𝐿𝐵, produces a NFA for inject(𝐿𝐴,𝐿𝐵). You may assume that 𝐴 and 𝐵 have unique accept states.
For submission, upload a single Python source file q2.py which defines func- tions q2a() and q2b(a, b).
• The function q2a() takes no arguments and must return a string.
• The function q2b(a, b) takes two arguments, each a DFA, and returns an NFA. The inputs will be instances of automata.fa.dfa.DFA, the return value must be an instance of automata.fa.nfa.NFA.
Task A
Your friend suggests the following method:
1. Takeacopyof𝐴andacopyof𝐵
2. Use the same initial state and accept state as 𝐴
3. For every state 𝑞𝑎 in 𝐴, add an 𝜖 transition to the start state of 𝐵 and an 𝜖 transition from the accept state of 𝐵 to 𝑞𝑎
The idea is that we process 𝑥 in 𝐴 and then jump to 𝐵 and after processing 𝑤 in 𝐵, we jump back to 𝐴 and process 𝑦 in 𝐴. For example, suppose 𝐿𝐴 is the set of even-length2 strings that are all 0s and 𝐿𝐵 is the set of even-length
1More verbosely: inject(𝐿𝐴, 𝐿𝐵) = {𝑠 ∈ Σ∗ ∣ ∃𝑥, 𝑦 ∈ Σ∗ ∃𝑤 ∈ 𝐿𝐵(𝑥𝑦 ∈ 𝐿𝐴 ∧ 𝑠 = 𝑥𝑤𝑦}. 2Recall that 0 is an even number.
stringsthatareall1s,i.e. 𝐿𝐴 ={02𝑛 ∣𝑛≥0}and𝐿𝐵 ={12𝑛 ∣𝑛≥0}. Then this is a DFA for 𝐴:
This is a DFA for 𝐵:
𝑞0
0
0
11 𝑞2
0, 1
𝑞1
𝑞1𝑞 34
1
00 𝑞5
0, 1
and this is the result of applying the above construction method:
1
𝑞0𝑞1𝑞
0 1 20,1
0
𝜖 𝜖
𝜖 𝜖𝜖
𝑞1𝑞 𝑞
3 4050,1
1
Your task is to show that this construction method does not work for the above example. In particular, write a function q2a() which returns a string that is accepted by the NFA above but is not in inject(𝐿𝐴,𝐿𝐵).
Task B
Write a function q2b(a, b) which returns an NFA for inject(𝐿𝐴,𝐿𝐵), where 𝐿𝐴 is the language of the DFA a and 𝐿𝐵 is the language of the DFA b.
Q3 Context-Free Languages: PDA and CFG Design
Consider the language
𝐿 = {𝑥𝑦 ∣ 𝑥,𝑦 ∈ Σ∗,|𝑥| = |𝑦|,𝑏 occurs in y}
where Σ = {𝑎, 𝑏}.
For submission, upload a single Python source file q3.py which defines func-
tions q3a() and q3b().
-
The function q3a() takes no arguments and must return an instance of
automata.pda.npda.NPDA.
-
The function q3b() takes no arguments, and returns a context-free gram- mar as a list of pairs (x, y) such that x is a string consisting of a single letter (representing a variable), and where y is a list of strings (represent- ing the right-hand sides of the rules). So, for example, the grammar
𝑆 → 𝑎𝑆𝑏 ∣ 𝐴 𝐴→𝜀
would become
[ ('S', ['aSb', 'A']),('A', ['']) ]
Remember that, by convention, the start variable of a grammar is the left-hand side of the first rule!
Task A
Write a function q3a() which returns a PDA that recognises 𝐿. Task B
Write a function q3b() which returns a context-free grammar for 𝐿.
Q4 Closure Properties
For all integers 𝑝, 𝑞 and 𝑟, the language
{𝑎𝑛𝑏𝑚 ∣𝑛,𝑚≥0,𝑛𝑝+𝑚𝑞=𝑟}
is context-free. Using this fact and the closure properties of context-free lan-
guages, prove that
𝐿={𝑎𝑛𝑏𝑚 ∣𝑛,𝑚≥0}
is also context-free. In your proof, do not use any languages other than these or those derived from these using closure properties. (Proofs violating this requirement will receive 0 marks.)
Q5 Pumping Lemma for Regular Languages
Using the pumping lemma for regular languages, prove that
𝐿={𝑎𝑛𝑏𝑚𝑐𝑘 ∣𝑛,𝑚,𝑘≥0,𝑛𝑚=2𝑘}
is not regular.
Q6 Pumping Lemma for Context-Free Languages
Let Σ = {𝑎,𝑏} and
𝐿={𝑤∈Σ∗ ∣forallnonempty𝑠∈Σ∗,thestring𝑠𝑠𝑠doesnotoccurin𝑤}.
The language 𝐿 is infinite. Using this fact and the pumping lemma for context- free languages, prove that 𝐿 is not context-free.
