COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 8: Chomsky Hierarchy
Before this tutorial you are expected to have read Section 11 of the Computing Theory notes. Aim
The aim of this tutorial is to give some insight into the relationships between context-free languages and other classes of languages. You should be able to complete all the questions below after this tutorial.
PART1: PushdownAutomata…………………………………………………………………… (a) Give a PDA for the following languages. Are any of these PDAs deterministic?
i. {aibjck |i=jorj=k,i,j,k≥0}
Solution: S → AB | CD A → aAb | λ
B → cB | λ
C → aC | λ
D → bDc | λ
a+A b−A c
q1 λ q2
q4 λ q5
a
λ q3
λ q0
λ
λ q6 b+A c−A
ii. {aibjck | i ̸= j,i,j,k ≥ 0}
Solution:
S → AD
A → aAb | B | C B → aB | a
C → bC | b
D → cD | λ
1
COSC1107/1105 – Computing Theory Tutorial 7: Chomsky Hierarchy Page 2 of 5
a+A b−A λ−A qλqλ−Aq
012
bλ
b q3 λ q4 c
iii. {aibjck | j ̸= k,i,j,k ≥ 0}
Solution:
S → EF
E → aE | λ
F → bF c | G | H G → bG | b
H → cH | c
a b+A c−A λ−A qλqλqλ−Aq
0123
c
q4 c
iv. {aibjck |i̸=jorj̸=k,i,j,k≥0}
Solution: Possible (combine previous two solutions)
a+A b−A λ−A
qλqλ−Aq 123
λbλ
q0 q4 λ q5 c b
λc qλqλqλ−Aq
6789
a
b+A c−A λ−A
PART2: ThePumpingLemmaforContext-freeLanguages…………………………………….. The Pumping Lemma for context-free languages is below.
For any context-free language L, there is an integer n ≥ 1 such that for all strings w ∈ L such that |w| ≥ n, there exist strings x, y, z, u and v such that w = xyzuv and
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 7: Chomsky Hierarchy Page 3 of 5
1. |yzu| ≤ n
2. y̸=λoru̸=λ
3. xyizuiv∈Lforalli≥0
Note that condition 2 is sometimes stated equivalently as |y| + |u| > 0, or that it is not the case that both y and u are λ. Prove that the following languages are not context-free.
(a) {aibici | i ≥ 0}
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Choosew = anbncn,andsow ∈ Land|w| ≥ n. SobythePumpingLemma,w = xyzuv = anbncn,and |yzu| ≤ n.
Now as |yzu| ≤ n, this means that y and u can only contain two different symbols – they are too short to contain a’s and b’s and c’s, as this would require them to have length at least n + 2.
Now if y or u contains ab, then xyyzuuv will contain ba somewhere. This means that xyyzuu ̸∈ L. Similarly if y or u contains bc then xyyzuuv will contain cb somewhere. This means that xyyzuu ̸∈ L.
So that means y and u can contain only a’s or only b’s or only c’s. We need to work through the possibilities here.
• If y contains only a’s and u contains only a’s or b’s, then xyyzuuv will contain more a’s then w, but the same number of c’s as w, and so xyyzuuv ̸∈ L.
• If y contains only b’s and u contains only b’s or c’s, then xyyzuuv will contain more b’s then w, but the same number of a’s as w, and so xyyzuuv ̸∈ L.
• If y contains only c’s and u contains only c’s, then xyyzuuv will contain more c’s then w, but the same number of a’s and b’s as w, and so xyyzuuv ̸∈ L.
So this exhausts all the possibilities for y and u, given that |yzu| ≤ n. This is a contradiction, and so L is not context-free. QED
(b) {aibjaibj |i,j≥0}
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Letw = anbnanbn,andsow ∈ Land|w| ≥ n. SobythePumpingLemma,w = xyzuv = anbnanbn and |yzu| ≤ n.
Nowas|yzu|≤n,thismeansthatyanduareeachoftheformakbl orbkal,wherek+l>0,ienotbothkandl are 0.
Now if y or u contains ab or ba, then xyyzuuv will not be of the form aibjaibj, as there will be at least three non-empty sequences of a’s and b’s.
So that means y and u can contain only a’s or only b’s. Now we need to work through the possibilities here.
• If y contains only a’s and u contains only a’s, then as |yzu| < n, y and u must both belong to the first cluster of a’s, or both to the second cluster. In the first case, xyyzuuv will have a mismatched number of a’s (more in the first cluster than the second) and so xyyzuuv ̸∈ L. In the second case, xyyzuuv will have a mismatched number of a’s (more in the second cluster than the first) and so xyyzuuv ̸∈ L.
• If y contains only a’s and u contains only b’s, then either both belong to the first cluster of a’s and b’s, or both belong to the second cluster of a’s and b’s. In the first case, xyyzuuv will have a mismatched number of a’s or b’s (more in the first cluster than the second), and so xyyzuuv ̸∈ L. In the second case, xyyzuuv will have a mismatched number of a’s or b’s (more in the second cluster than the first) and so xyyzuuv ̸∈ L.
RMIT CT 2021 (Semester 2) - Exercise 2 continues on the next page. . .
COSC1107/1105 - Computing Theory Tutorial 7: Chomsky Hierarchy Page 4 of 5
• Ifycontainsonlyb’sanducontainsonlya’s,thenymustbelongtothefirstclusterofb’s,andutothesecond cluster of a’s. So xyyzuuv will have a mismatched number of b’s (more in the first cluster than the second) or a mismatched number of a’s (more in the second cluster than the first), and so xyyzuuv ̸∈ L.
• If y contains only b’s and u contains only b’s, then as |yzu| < n, y and u must both belong to the first cluster of b’s, or both to the second cluster. In the first case, xyyzuuv will have a mismatched number of b’s (more in the first cluster than the second) and so xyyzuuv ̸∈ L. In the second case, xyyzuuv will have a mismatched number of b’s (more in the second cluster than the first) and so xyyzuuv ̸∈ L.
So this exhausts all the possibilities for y and u, given that |yzu| ≤ n. This is a contradiction, and so L is not context-free. QED
(c) {uu | u ∈ {a,b}∗}
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Let w = anbnanbn, and so w ∈ L and |w| ≥ n. So by the Pumping Lemma, w = xyzuv = anbnanbn, and |yzu| ≤ n.
This means that there are four cases to consider.
• Case 1: yzu = ar for some r ∈ Z (fully contained within either the first or second group of a’s).
• Case 2: yzu = br for some r ∈ Z (fully contained within either the first or second group of b’s).
• Case 3: yzu = ar bs for some r, s ∈ Z (fully contained within either the first or second half of w).
• Case 4: yzu = br as for some r, s ∈ Z (encompassing the centre of w).
• The second is when yzu occurs in the ’middle’ 2n + 1 characters of w. In this case, there are three further possibilities.
Consider now i = 0 and the string xyizuiv = xy0zu0v = xzv.
Note that in all cases we have xyizuiv ̸∈ L as:
– Case 1: xzv will have less a’s in the exterior than in the interior (or vice-versa), i.e. xzv = aebf agbf where e ̸= f.
– Case 2: xzv will have less b’s in the interior than in the exterior (or vice-versa), i.e. xzv = aebf aebg where f ̸= g.
– Case 3: xzv will have less a’s or b’s in first half of w than in the second half (or vice-versa), i.e. xzv = aebf agbh where e ̸= g or f ̸= h.
– Case4:xzvwillhavelessa’sintheexteriorthanintheinterior(orvice-versa),i.e.i.e.xzv=aebfagbh wheree̸=gorf ̸=h.
• The third is when yzu occurs in the last 2n + 1 characters of w. In this case, when i = 0, we have xy0zu0v will be of the form anbn+1s where |s| < 2n + 1. This means thatxy0zu0v ̸∈ L, as it is not of the form uu.
So this exhausts all the possibilities for y and u, given that |yzu| ≤ n. This is a contradiction, and so L is not context-free. QED
(d) {am | m is prime}
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Choosew = ap wherepisaprime> n,andsow ∈ Land|w| ≥ n. SobythePumpingLemma,w = xyzuv = ap, and |yzu| ≤ n.
Let i = p+1. So |xyp+1zup+1v| = |xyzuv|+|yp|+|up| = |xyzuv|+p(|y|+|u|) = p+p(|y|+|u|) = p(1+|y|+|u|). So |xyp+1zup+1v| is not prime, as it is the product of two factors, neither of which can be 1.
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 7: Chomsky Hierarchy Page 5 of 5
This is a contradiction, and so L is not context-free. QED (e) {am | m = n2} for some integer n.
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Choosew=am wherem=n2,andsow∈Land|w|≥n.SobythePumpingLemma,w=xyzuv=an2,and |yzu| ≤ n.
Now |xy2zu2v| = |xyzuv| + |y| + |u| = n2 + |y| + |u|, and as |yzu| ≤ n, this means that n2 = |xyzuv| < |xy2zu2v|≤n2 +n<(n+1)2.
So |xy2zu2v| is not a square.
This is a contradiction, and so L is not context-free.QED
(f) {w | w ∈ {a,b,c}∗,na(w) = nb(w) = nc(w)}
Solution:
Assume that L is context-free. Then the Pumping Lemma applies and so there is an n ≥ 1 such that for all w ∈ L with |w| ≥ n, there exist strings x, y, z, u and v such that
1. w = xyzuv
2. |yzu| ≤ n
3. y̸=λoru̸=λ
4. xyizuiv∈Lforalli≥0
Choosew = anbncn,andsow ∈ Land|w| ≥ n. SobythePumpingLemma,w = xyzuv = anbncn,and |yzu| ≤ n.
Now as |yzu| ≤ n, this means that y and u can only contain two different symbols – they are too short to contains a’s and b’s and c’s, as this would require them to have length at least n + 2. Moreover, only one of y and u can contain more than one different symbol, as they are also two short to ’span’ more than one boundary between the different symbols in anbncn.
Now consider xyyzuuv which will either contain more a’s than c’s, more b’s than a’s or more c’s than a’s. Whichever of these is true we have that xyyzuuv ̸ inL.
This is a contradiction, and so L is not context-free. QED
RMIT CT 2021 (Semester 2) -
End of tutorial worksheet