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
, length(v) + length(y) > 0
and where all words of the form uvnxynz with n > 1 are also in the language.
1. We should next choose a suitable word from L which is long enough. The
word a2pb3.2pa2p seems a good choice: it is in L and it has more than 2p
characters. Let us examine all the different ways in which the word a2pb3.2pa2p
can be divided up into five parts. Remember that vxy cannot have more than
2p characters. This means that there are five ways in which vxy can occur in
the word:
(a) fully from the first 2p characters (thus consists of as only),
(b) covering some of the first as and also some of the bs,
(c) fully from the group of bs,
(d) covering some characters of the group of bs and some characters of
the final group of as,
(e) fully from the second group of as.
We now examine each of these five possibilities. We are going to show that
the pumped word will in none of these cases be of the form anb3nan.
(a) Suppose vxy consists of as only from the first group of as. According to the
pumping lemma with length the word uvvxyyz must also be in the language L.
This word will now have more than 2p as at the beginning of the word followed
by b3.2pa2p and will not be of the form anb3nan. Such a word is not in L.
(b) Suppose vxy consists of as followed by bs. According to the pumping lemma
with length the word uvvxyyz must also be in the language L. What will this
(pumped) word look like? Well, there are several possibilities.
• If v consists of as only and y consists of bs only, the pumped word will
have more than 2p as at the beginning of the word followed by more than
3.2p bs, followed by a2p. The word is not of the form anb3nan and is thus not
in L.
• If v consists of as and bs, and y of bs only, the pumped word will have
more than 2p as followed by more than 3.2p bs, followed by 2p as. There
will also be more ab-substrings than allowed. The word is not of the form
anb3nan and thus not in L.
• The same problem will occur if v consists of as only and y consists of as
and bs, because the pumped word will have more than 2p as, followed by
more than 3.2p bs and more than 2p as followed by a2p. There will also be
more ab-substrings than allowed. The word is not of the form anb3nan and
thus not in L.
• In any of the above mentioned three possible cases either v or y may be
empty (both cannot be empty – are you able to explain why not?), but still
the pumped word will not be a permissible word in L.
(c) Suppose vxy consists of bs only. According to the pumping lemma with length
the word uvvxyyz must also be in the language L. This word will now have 2p
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
, length(v) + length(y) > 0
and where all words of the form uvnxynz with n > 1 are also in the language.
1. We should next choose a suitable word from L which is long enough. The
word a2pb3.2pa2p seems a good choice: it is in L and it has more than 2p
characters. Let us examine all the different ways in which the word a2pb3.2pa2p
can be divided up into five parts. Remember that vxy cannot have more than
2p characters. This means that there are five ways in which vxy can occur in
the word:
(a) fully from the first 2p characters (thus consists of as only),
(b) covering some of the first as and also some of the bs,
(c) fully from the group of bs,
(d) covering some characters of the group of bs and some characters of
the final group of as,
(e) fully from the second group of as.
We now examine each of these five possibilities. We are going to show that
the pumped word will in none of these cases be of the form anb3nan.
(a) Suppose vxy consists of as only from the first group of as. According to the
pumping lemma with length the word uvvxyyz must also be in the language L.
This word will now have more than 2p as at the beginning of the word followed
by b3.2pa2p and will not be of the form anb3nan. Such a word is not in L.
(b) Suppose vxy consists of as followed by bs. According to the pumping lemma
with length the word uvvxyyz must also be in the language L. What will this
(pumped) word look like? Well, there are several possibilities.
• If v consists of as only and y consists of bs only, the pumped word will
have more than 2p as at the beginning of the word followed by more than
3.2p bs, followed by a2p. The word is not of the form anb3nan and is thus not
in L.
• If v consists of as and bs, and y of bs only, the pumped word will have
more than 2p as followed by more than 3.2p bs, followed by 2p as. There
will also be more ab-substrings than allowed. The word is not of the form
anb3nan and thus not in L.
• The same problem will occur if v consists of as only and y consists of as
and bs, because the pumped word will have more than 2p as, followed by
more than 3.2p bs and more than 2p as followed by a2p. There will also be
more ab-substrings than allowed. The word is not of the form anb3nan and
thus not in L.
• In any of the above mentioned three possible cases either v or y may be
empty (both cannot be empty – are you able to explain why not?), but still
the pumped word will not be a permissible word in L.
(c) Suppose vxy consists of bs only. According to the pumping lemma with length
the word uvvxyyz must also be in the language L. This word will now have 2p
