COS3701
EXAM PACK
FOR ASSISTANCE WITH THIS MODULE +27 67 171 1739
,Question 1
Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0} is deterministic
context free.
Solution
For this DPDA we have
∑ = {a, b, Λ}
Г = {X, Λ}
In this DPDA the first ab substring (which must exist by the definition of the
language) is read and an X is pushed onto the stack.
Then subsequent ab substrings are read (each time pushing an X onto the stack)
until the first b in the first ba substring is read. At this point the second part of the
DPDA starts working to recognise the ba substrings.
An X is popped off the stack for each ba found.
When the first a of the aa substring is read the DPDA reads the next a, then reads a
blank a and then checks that all the Xs have been popped off the stack. If there were
still any Xs on the stack then the number of ab and ba substrings would not have
been the same and the word would not be in the language.
Suppose we are given the word ababbabaaa. The first a and the first b will be read
by the two Reads before the Push. Then a X will be pushed onto the stack. Then the
next ab will be read before pushing another X onto the stack. At this point the stack
contains two Xs – one for each ab substring.
Then a b is read an the DPDA starts processing the ba substrings (this is done by
the loop in the middle of the figure). As each ba is read an X is popped off the stack.
When an a is read then the DPDA expects another a and then so it reads that.
After two as the input tape and the stack must both be empty and so the DPDA
checks both of these.
Check using other words in the language that the DPDA is correct.
The following Figure 1 shows a DPDA which recognises the language.
, Figure 1
Question 2
Prove that the language L = {anb3nan} is non-context free. Use the pumping lemma
with length.
Solution
The first step is to assume that the language L = {anb3nan | n = 1; 2; 3; ...}
actually is context free. This means that there exists a CFG in Chomsky
Normal Form (CNF) with, say, p live productions which generates the
language. Because we assume that the language is context free, we may
apply the pumping lemma.
According to the pumping lemma with length any word w in L with more than
2p characters can be broken up into five parts, i.e. the word can be written as
w = uvxyz, with
length(vxy) ≤ 2p and
length(x) > 0 and
EXAM PACK
FOR ASSISTANCE WITH THIS MODULE +27 67 171 1739
,Question 1
Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0} is deterministic
context free.
Solution
For this DPDA we have
∑ = {a, b, Λ}
Г = {X, Λ}
In this DPDA the first ab substring (which must exist by the definition of the
language) is read and an X is pushed onto the stack.
Then subsequent ab substrings are read (each time pushing an X onto the stack)
until the first b in the first ba substring is read. At this point the second part of the
DPDA starts working to recognise the ba substrings.
An X is popped off the stack for each ba found.
When the first a of the aa substring is read the DPDA reads the next a, then reads a
blank a and then checks that all the Xs have been popped off the stack. If there were
still any Xs on the stack then the number of ab and ba substrings would not have
been the same and the word would not be in the language.
Suppose we are given the word ababbabaaa. The first a and the first b will be read
by the two Reads before the Push. Then a X will be pushed onto the stack. Then the
next ab will be read before pushing another X onto the stack. At this point the stack
contains two Xs – one for each ab substring.
Then a b is read an the DPDA starts processing the ba substrings (this is done by
the loop in the middle of the figure). As each ba is read an X is popped off the stack.
When an a is read then the DPDA expects another a and then so it reads that.
After two as the input tape and the stack must both be empty and so the DPDA
checks both of these.
Check using other words in the language that the DPDA is correct.
The following Figure 1 shows a DPDA which recognises the language.
, Figure 1
Question 2
Prove that the language L = {anb3nan} is non-context free. Use the pumping lemma
with length.
Solution
The first step is to assume that the language L = {anb3nan | n = 1; 2; 3; ...}
actually is context free. This means that there exists a CFG in Chomsky
Normal Form (CNF) with, say, p live productions which generates the
language. Because we assume that the language is context free, we may
apply the pumping lemma.
According to the pumping lemma with length any word w in L with more than
2p characters can be broken up into five parts, i.e. the word can be written as
w = uvxyz, with
length(vxy) ≤ 2p and
length(x) > 0 and
