COMP 330 Winter 2021 Assignment 2 Solutions
Prakash Panangaden
Question 1[20 points]
Give regular expressions for the following languages over {a, b}:
1. {w|w contains an even number of occurrences of a} 2. {w|w contains an odd number of occurrences of b} 3. {w| does not contain the substring ab}
4. {w| does not contain the substring aba}
Solution
• (b∗ab∗ab∗)∗ + b∗
• (a∗ba∗)(ba∗ba∗)∗
• b∗a∗
• b∗a∗(bbb∗a∗)∗b∗. Another equivalent expression is b∗+b∗aa∗(bbb∗aa∗)∗b∗.
The last one is quite tricky. An a can be followed by two or more b’s but not by a single b if you want more a’s later.
Question 2[20 points]
Suppose that you have a DFA M = (S,Σ,s0,δ,F). Consider two distinct states s1,s2 i.e. s1 ̸= s2. Suppose further that for all a ∈ Σ δ(s1,a) = δ(s2,a). Show that for any nonempty word w over Σ we have δ∗(s1,w) = δ∗(s2, w).
Solution We proceed by induction on the length of the word. The base case is when w has length 1, i.e. it is a single letter. This means we must show:
∀a ∈ Σ, δ∗(s1, a) = δ∗(s2, a). 1
From the definition of δ∗ this becomes just
∀a ∈ Σ,δ(s1,a) = δ(s2,a).
But this was given to us in the problem so the base case is immediately verified.
The inductive hypothesis is that
∀w ∈ Σ∗, |w| < n implies δ∗(s1, w) = δ∗(s2, w).
Now we consider a word of the form wa where w has length n−1 and a is any letter in Σ.
δ∗(s1, wa) = δ(δ∗(s1, w), a) = δ(δ∗(s2, w), a) = δ∗(s2, wa).
The first equation follows from the definition of δ∗, the second follows from the inductive hypothesis and the last from the definition of δ∗. This verifies the inductive case; we are done.
Question 3[20 points]
Show that the following languages are not regular by using the pumping lemma.
1. {anbman+m|n, m ≥ 0},
2. {x|x = xR,x ∈ Σ∗}, where xR means x reversed; these strings are
called palindromes. An example is abba, a non-example is baba.
Solution
1. The demon picks a number p. I pick the string apba(p+1). Whatever the demon tries to do he is forced to pick y to consist of a nonempty string that consists exclusively of as, because |xy| ≤ p and |y| > 0, say that y = al. Now I choose i = 3. The new string is a(p+2l)ba(p+1) which is not in the language since 2l ̸= 1. My strategy is sure to work because I have taken into account anything that the demon might do.
2. Suppose the demon picks the number p. I choose the string apbbap which is a palindrome. Now the demon tries to divide it up into x, y, z with |xy| ≤ p, |y| > 0, in such a way that xyiz a palindrome for all i≥0. Itmustbethecasethatx=ak forsomek∈{0,…,p−1}, y = aj for some j ∈ {1,…,p} and z = albbap for some l ∈ {0,…,p−1}. Now I choose i = 2 and we see that xy2z = ap+jbbap, which is not a palindrome, since j > 0. Therefore, this language is not regular.
2
Question 4[20 points] Show that the following languages are not regular by using the pumping lemma.
1. {x ∈ {a, b, c}∗||x| is a square.} Here |x| means the length of x.
2. {a2nbn}. Solution
1. The demon picks some p. I choose the string ap2 which has length p2 which is indeed a square. Now the demon has to pick y to consist of a’s exclusively because there are no other letters in the string. Let |y|=q>0andq≤p. NowIchoosei=2. Thenwegetap2+q asthe pumped string. This string has length p2 + q. Now q ≤ p < 2p + 1, hence p2 +q < p2 +2p+1 = (p+1)2. Thus p2 +q cannot be a square since it is strictly less than the next square after p2. Thus, I win and the language is not regular.
2. The demon picks some p. I pick a2pbp. The demon is forced to pick y consistingexclusivelyofa’sand|y|≤p;let|y|=q>0. Ipicki=0 so the “pumped” string is a2p−qbp and clearly this string is not in the language.
Question 5[20 points] We are using the alphabet {0,1}. We have a DFA with 5 states, S = {s0, s1, s2, s3, s4}. The start state is s0 and the only accepting state is also s0. The transitions are given by the formula
δ(si,a)=sj wherej=i2+a mod5.
Draw the table showing which pairs of states are inequivalent and then construct the minimal automaton. Remember to remove useless states right from the start, before you draw the table. I am happy with a drawing of the automaton.
Solution Here is the original automaton:
3
1
s1 1 s2
1
1
1 0
s3 0 s4
00
start s0
It is clear from this picture that s3 is an unreachable state so we remove it right away.
Here is the table:
After running the algorithm the pairs that cannot be equivalent are marked with an X. The diagonal is marked with a / and of course we do not need to do anything above the diagonal. There is only one pair left unmarked. According to the algorithm, these states are equivalent. This means that s1 and s4 can be lumped together to give a 3-state machine. The minimized machine is shown below:
0
s4 s2 s1 s0
/
/ x
/ x x
/ x P x
s0
s1
s2
s4
00
0
start
s0 s14 s2 11
1
4