COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 7: Nondeterminism and the Pumping Lemma
Before this tutorial you are expected to have read Section 11 and 12 of the Computing Theory notes. Aim
The aim of this tutorial is to explore more deeply the concept of non-determinism. By the end of this tutorial you should be able to convert a given NFA into an equivalent DFA and to use the Pumping Lemma to show that a given language is not regular.
PART1: Non-determinism……………………………………………………………………….
(a) Give a DFA for each of the following languages. It might be easier to construct a NFA first and then convert to DFA for some of the regular expressions.
i. (ab)∗ba
ii. (ab)∗(ba)∗
iii. aa(a|b)+bb
Solution:
q1 q3 q0 b q2
Solution:
q1 q3 q0 b q2
Solution:
a,b
q a q a q a,b q q a q a q a,b q
01230123
a
a
bb
q5 q4 bq5 q4 bb
iv. ((aa)+bb)∗ Solution:
1
a
a
a
b a
a
b
b
COSC1107/1105 – Computing TheoTruytorial 7: Nondeterminism and the Pumping Lemma Page 2 of 6
e a,b aq3 b
q0 a q1 a q2
λb q5
0 05
14
2a3 a
a b
q4
v. (ab∗a)∗
(b) The regular expression a∗b∗ has a very simple NFA. This is shown in the following transition table (not the following image). The final state is q1 and q0 is the beginning state. Convert this NFA to a DFA.
Solution:
bb
a
q1 1 a 02
a,b
q0 q2 0 b e λ
q1
0,1 q0
q1
abλ q0q0 q1
Solution:
a,b q0 b q1 a e
ab
(c) Give a DFA for the following NFAs:
i.
0 q1
1 q2
Solution:
1
0
0
02 0 01 1
RMIT CT 2021 (Semester 2) –
Exercise 1 continues on the next page. . .
b
a
b
b
aa
a
b
b
0
1
a
a
a
b
COSC1107/1105 – Computing TheoTruytorial 7: Nondeterminism and the Pumping Lemma
Page 3 of 6
ii.
012
01
10 q 0 q 0,1 q
Solution:
1 12
0 0 1 0 02 e 0,1
q
1 1
0,1 q 0,1 q 012
q3
iii.
Solution:
1 1 12
1 012
0
123 0 23
3
e 13 0 2 1 0,1
0
0
RMIT CT 2021 (Semester 2) –
Exercise 1 continues on the next page. . .
1
0
1
1
0
0
0 1
0
1
0
0
1
1
0
0
1
1
1
COSC1107/1105 – Computing TheoTruytorial 7: Nondeterminism and the Pumping Lemma
Page 4 of 6
aa
q1 b q2 λ
q0
λ
iv.
q3 a q4 bb
Solution:
a
1
a,b 013 24 e
23 4
b
14 2
3
b
a
PART2: ThePumpingLemma………………………………………………………………….. (a) The Pumping Lemma for regular languages is below.
For any regular language L, there is an n ≥ 1 such that for all w ∈ L such that |w| ≥ n, there exists strings x, y and z such that w = xyz and
• |xy|≤n
• y ̸= λ
• xyiz∈L∀i≥0
How would you make use of this result?
(b) Suppose that L a regular language. What is the smallest number n in the Pumping Lemma length condition, that is, the smallest n such that every word in L longer than n, can be split into ….
Solution:
It is generally used to prove non-regularity of a language, that is, to prove that the language is not regular. This is important both theoretically and practically. You say why practically? Check it here.
However, there are also some ’positive’ uses of this result (see an exercise below).
Solution:
The n is the number of states of the smallest DFA that recognizes the language. If the length is more than n, then it must have repeated some state, hence the loop, hence the ability to “pump” that cycle as many times as we wanted (including removing it!).
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
aa
aa
aa
bb
bb
bb
COSC1107/1105 – Computing TheoTruytorial 7: Nondeterminism and the Pumping Lemma Page 5 of 6
(c) Consider the statement below. Do you think this is true? If so, why? If not, why not? How would you settle this question?
For any regular language L, there is an n ≥ 1 such that for all w ∈ L such that |w| ≥ n, there is another string v ∈ L such thate |v| < n.
(d) Let L be a regular language over {0, 1}. Show how we can use the previous result to show that in order to determine whether or not L is empty, we need only test at most 2n − 1 strings.
(e) Use the Pumping Lemma for each of the following: i. Show that {anbn|n ≥ 0} is not regular.
ii. Show that {an|n is a prime number} is not regular.
iii. Show that {an|n is a perfect square} is not regular.
iv. Show that the set of palindromes over |a, b| is not regular.
v. Show that {anbm|n < m} is not regular.
Solution: This follows from the Pumping Lemma. As L is regular, the Pumping Lemma applies, i.e. ∃n ≥ 1 such that for all w ∈ L such that |w| ≥ n, w = xyz, |xy| ≤ n, y ̸= λ and xyiz ∈ L for all i ≥ 0. Now, note what happens when i = 0. When i = 0 we have xz ∈ L and |xz| < |xyz|. Now if |xz| < n, then v = xz and we are done. Otherwise as |xz| ≥ n, we can apply the Pumping Lemma again to show that there is another string t such that t ∈ L and |t| < |xz|. Using this argument repeatedly means we eventually conclude there is a string v ∈ L with |v| < n.
Solution: If L is not empty, the previous result shows there is a string w ∈ L with |w| < n. If L is empty there is no string w ∈ L with |w| < n. So we only need to test strings of length 0, 1, 2, ..., n − 1, and if there are no such stringsinL,Lisempty.Thisisatotalof1+2+4+...+2n−1 =2n −1strings.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
Letw=anbn. Thenw∈Land|w|>n,andsow=xyz. As|xy|≤n,yisoftheformaj forsome 1 ≤ j ≤ n. Hence xyyz ∈ L, i.e. a(n+j)bn ∈ L, which is a contradiction. Hence L is not regular.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
Letw=am wheremisanyprimelargerthann.Thenwehavew=am =xyz,y̸=eandxyiz∈Lforall i ≥ 0. Let i = m+1. Then |xyiz| = |xym+1z| = |xyz|+|ym| = m+m|y| = m(1+|y|). Hence |xym+1z| is not prime, and so |xym+1z| ̸∈ L which is a contradiction.
Hence L is not regular.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
Letw=ak2 wherek>n.Thenwehavew=ak2 =xyz,y̸=eandxyiz∈Lforalli≥0.Nowask>n, wehave|xy|≤n
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
RMIT CT 2021 (Semester 2) –
Exercise 2 continues on the next page. . .
COSC1107/1105 – Computing TheoTruytorial 7: Nondeterminism and the Pumping Lemma Page 6 of 6
Let w = anbn+1. Then w ∈ L and |w| > n, and so w = xyz. As |xy| ≤ n, y is of the form aj for some 1 ≤ j ≤ n. Hence xyyyz ∈ L, i.e. an+2jbn+1 ∈ L, which is a contradiction, as j ≥ 1.
Hence L is not regular.
vi. Show that {anbman|n, m ≥ 0} is not regular.
vii. Show that {ww|w is any string over {a, b}} is not regular.
viii. Show that {an|n is a perfect cube } is not regular.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
Letw=anban. Thenw∈Land|w|>n,andsow=xyz.As|xy|≤n,yisoftheformaj forsome 1 ≤ j ≤ n. Hence xyyz ∈ L, i.e. an+j ban ∈ L, which is a contradiction.
Hence L is not regular.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0. Letw=banban.Thenw∈Land|w|>n,andsow=xyz.As|xy|≤n,yiseitheroftheformbaj for some0 ≤ j < norisoftheformaj forsome1 ≤ j ≤ n. Hencexyyz ∈,i.e.eitherbajbajan−jban = bajbanban ∈ L or banajban ∈ L, which, in either case, is a contradiction.
Hence L is not regular.
Solution:
Proof: Assume that L is regular. Then the Pumping Lemma applies, i.e. that ∃n such that for all w ∈ L with |w| ≥ n, w = xyz, y ̸= e, |xy| ≤ n and xyiz ∈ L for all i ≥ 0.
Letw=ak3 wherek>n.Thenwehavew=ak3 =xyz,y̸=eandxyiz∈Lforalli≥0.Nowask>n, wehave|xy|≤n