Microsoft Word – Solutions_ContextFreeLanguages.docx
Chapter 11 1
Part III: Context-Free Languages and Pushdown Automata
1 Context-Free Grammars
6) Show a context-free grammar for each of the following languages L:
a) BalDelim = {w : where w is a string of delimeters: (, ), [, ], {, }, that are properly balanced}.
S ® ( S ) | [ S ] | { S } | S S | e
b) {aibj : 2i = 3j + 1}.
S ® aaaSbb | aab
c) {aibj : 2i ¹ 3j + 1}.
We can begin by analyzing L, as shown in the following table:
# of a’s Allowed # of b’s
0 any
1 any
2 any except 1
3 any
4 any
5 any except 3
6 any
7 any
8 any except 5
S ® aaaSbb
S ® aaaX /* extra a’s
S ® T /* terminate
X ® A | A b /* arbitrarily more a’s
T ® A | B | a B | aabb B /* note that if we add two more a’s we cannot add just a single b.
A ® a A | e
B ® b B | e
d) {w Î {a, b}* : #a(w) = 2 #b(w)}.
S ® SaSaSbS
S ® SaSbSaS
S ® SbSaSaS
S ® e
e) {w Î {a, b}* : w = wR}.
S ® aSa
S ® bSb
S ® e
S ® a
S ® b }
Chapter 11 2
f) {aibjck : i, j, k ³ 0 and (i ¹ j or j ¹ k)}.
S ® XC /* i ¹ j
S ® AY /* j ¹ k
X ® aXb
X ® A¢ /* at least one extra a
X ® B¢ /* at least one extra b
Y ® bYc | B¢ | C¢
A¢ ® a A¢ | a
B¢ ® b B¢ | b
C¢ ® c C¢ | c
A ® a A | e
C ® c C | e }
g) {aibjck : i, j, k ³ 0 and (k £ i or k £ j)}.
S ® A | B
A ® aAc | aA | M
B ® aB | F
F ® bFc | bF | e
M ® bM | e
h) {w Î {a, b}* : every prefix of w has at least as many a’s as b’s}.
S ® aS | aSb | SS |e
i) {anbm : m ³ n, m-n is even}.
S ® aSb | S ® Sbb | e
j) {ambncpdq : m, n, p, q ³ 0 and m + n = p + q}.
For any string ambncpdq Î L, we will produce a’s and d’s in parallel for a while. But then one of two things
will happen. Either m ³ q, in which case we begin producing a’s and c’s for a while, or m £ q, in which case
we begin producing b’s and d’s for a while. (You will see that it is fine that it is ambiguous what happens if
m = q.) Eventually this process will stop and we will begin producing the innermost b’s and c’s for a while.
Notice that any of those four phases could produce zero pairs. Since the four phases are distinct, we will
need four nonterminals (since, for example, once we start producing c’s, we do not want ever to produce any
d’s again). So we have:
S ® aSd
S ® T
S ® U
T ® aTc
T ® V
U ® bUd
U ® V
V ® bVc
V ® e
Chapter 11 3
k) {xcn : x Î {a, b}* and (#a(x) = n or #b(x) = n)}.
S® A | B
A ® B¢ a B¢ A c | B¢
B¢ ® bB¢ | e
B ® A¢ b A¢ B c | A¢
A¢ ® aA¢ | e
l) {bi#bi+1R : bi is the binary representation of some integer i, i ³ 0, without leading zeros}. (For example
101#011 Î L.)
L can be written as:
0#1 È {1k#0k1 : k > 0} È {u01k#0k1uR : k ³ 0 and u Î 1(0 È 1)*}
So a grammar for L is:
S ® 0#1 | 1 S1 1 | 1 S2 1
S1 ® 1 S1 0 | #0
S2 ® 1 S2 1 | 0 S2 0 | 0 A 1
A ® 1 A 0 | #
m) {xR#y : x, y Î {0, 1}* and x is a substring of y}.
S ® S0 | S1 | S1
S1 ® 0S10 | 1S11 | T
T ® T1 | T0 | #
8) Consider the unambiguous expression grammar G¢ of Example 11.19.
a. Trace a derivation of the string id+id*id*id in G¢.
E Þ E + T Þ T + T Þ F + T Þ id + T Þ id + T * F Þ id + T * F * F Þ id + F * F * F Þ
id + id * F * F Þ id + id * id * F Þ id + id * id * id
b. Add exponentiation (**) and unary minus (-) to G¢, assigning the highest precedence to unary minus,
followed by exponentiation, multiplication, and addition, in that order.
R = { E ® E + T
E ® T
T ® T * F
T ® F
F ® F ** X
F ® X
X ® -X
X ® Y
Y ® (E)
Y ® id }.
Chapter 11 4
17) Consider the grammar G¢ of Example 11.19.
a) Convert G¢ to Chomsky normal form.
Remove-units produces:
E ® E + T | T * F | (E) | id
T ® T * F | (E) | id
F ® (E) | id
Then the final result is:
E ® E E1 | T E2 | T( E3 | id
T ® T E2 | T( E3 | id
F ® T( E3 | id
E1 ® T+ T
E2 ® T* F
E3 ® E T)
T( ® (
T)® )
T+ ® +
T* ® *
b) Consider the string id*id+id.
i) Show the parse tree that G¢ produces for it.
ii) Show the parse tree that your Chomsky normal form grammar produces for it.
i) E ii) E
E + T E E1
T F T E2 T+ T
T * F id id T* F + id
F id * id
id
18) Convert each of the following grammars to Chomsky Normal Form:
a) S ® a S a
S ® B
B ® b b C
B ® b b
C ® e
C ® c C
Chapter 11 5
Step 1: get rid of e productions:
Nullable variables: C
S ® a S a
S ® B
B ® b b C
B ® b b
C ® c C
C ® c
Step 2: eliminate unit productions:
Remove S ® B:
S ® a S a
S ® b b C
S ® b b
B ® b b C
B ® b b
C ® c C
C ® c
Step 3: eliminate terminals whenever the
length of the right hand side is greater than 1:
S ® Ta S Ta
S ® Tb Tb C
S ® Tb Tb
B ® Tb Tb C
B ® Tb Tb
C ® Tc C
C ® c
Ta ® a
Tb ® b
Tc ® c
Step 4: Eliminate long rules:
S ® Ta S¢
S¢ ® S Ta
S ® Tb S¢¢
S¢¢ ® Tb C
S ® Tb Tb
B ® Tb B¢
B¢ ® Tb C
B ® Tb Tb
C ® Tc C
C ® c
Ta ® a
Tb ® b
Tc ® c
Note that our algorithm retains the rules with
B on the left hand side. But they will never
be used in any derivation because they are
unreachable from S. If you want, you can add
a simplification step that removes
unreachable rules, which would yield:
S ® Ta S¢
S¢ ® S Ta
S ® Tb S¢¢
S¢¢ ® Tb C
S ® Tb Tb
C ® Tc C
C ® c
Ta ® a
Tb ® b
Tc ® c
b) S ® ABC
A ® aC | D
B ® bB | e | A
C ® Ac | e | Cc
D ® aa
Chapter 11 6
S ® AS1
S1 ® BC
S ® AC
S ® AB
S ® XaC | a | XaXa
A ® XaC
A ® a
A ® XaXa
B ® XbB
B ® b
B ® e
B ® XaC | a | XaXa
C ® AXc
C ® e
C ® CXc
C ® c
D ® XaXa
Xa ® a
Xb ® b
Xc ® c
c) S ® aTVa
T ® aTa | bTb | e | V
V ® cVc | e
S ® AS1 | AS2 | AS3 | AA
S1 ® TS2
S2 ® VA
S3 ® TA
T ® AA | BB | CC | CT1 | AS3 | BT2
T2 ® TB
V ® CT1 | CC
T1 ® VC
A ® a
B ® b
C ® c
Chapter 13 7
2 Pushdown Automata
1) Build a PDA to accept each of the following languages L:
a) BalDelim = {w : where w is a string of delimeters: (, ), [, ], {, }, that are properly balanced}.
M = ({1}, {(, ), [, ], {, }}, {(, [, {}, D, 1, {1}), where D =
{ ((1, (, e), (1, ()),
((1, [, e), (1, [)),
((1, {, e), (1, {)),
((1, ), )), (1, e)),
((1, ], ]), (1, e)),
((1, }, }), (1, e)) }
b) {aibj : 2i = 3j + 1}.
a/e/aa b/aaa/e
e/e/e e/a/e
c) {w Î {a, b}* : #a(w) = 2×#b(w)}.
The idea is that we only need one state. The stack will do all the work. It will count whatever it is ahead on.
Since one a matches two b’s, each a will push an a (if the machine is counting a’s) and each b (if the
machine is counting a’s) will pop two of them. If, on the other hand, the machine is counting b’s, each b
will push two b’s and each a will pop one. The only tricky case arises with inputs like aba. M will start out
counting a’s and so it will push one onto the stack. Then comes a b. It wants to pop two a’s, but there’s
only one. So it will pop that one and then switch to counting b’s by pushing a single b. The final a will then
pop that b. M is highly nondeterministic. But there will be an accepting path iff the input string w is in L.
M = ({1}, {a, b}, {a, b}, D, 1, {1}), where D =
{ ((1, a, e), (1, a)),
((1, a, b), (1, e)),
((1, b, e), (1, bb)),
((1, b, aa), (1, e)),
((1, b, a), (1, b)) }
d) {anbm : m £ n £ 2m}.
M = ({1, 2}, {a, b}, {a}, D, 1, {1, 2}), where D =
{ ((1, a, e), (1, a)),
((1, e, e), (2, e)),
((2, b, a), (2, e)),
((2, b, aa), (2, e)) }.
e) {w Î {a, b}* : w = wR}.
This language includes all the even-length palindromes of Example 12.5, plus the odd-length palindromes.
So a PDA to accept it has a start state we’ll call 1. There is a transition, from 1, labeled e/e/e, to a copy of
Chapter 13 8
the PDA of Example 12.5. There is also a similarly labeled transition from 1 to a machine that is identical
to the machine of Example 12.5 except that the transition from state s to state f has the following two labels:
a/e/e and b/e/e. If an input string has a middle character, that character will drive the new machine through
that transition.
Chapter 13 9
3 Context-Free and Noncontext-Free Languages
1) For each of the following languages L, state whether L is regular, context-free but not regular, or not context-free
and prove your answer.
a) {xy : x, y Î {a, b}* and |x| = |y|}.
Regular. L = {w Î {a, b}* : |w| is even}
= (aa È ab È ba È bb)*
b) {(ab)nanbn : n > 0}.
Not context-free. We prove this with the Pumping Theorem. Let w = (ab)kakbk. Divide w into three regions:
the ab region, the a region, and the b region. If either v or y crosses the boundary between regions 2 and 3
then pump in once. The resulting string will have characters out of order. We consider the remaining
alternatives for where nonempty v and y can occur:
(1, 1) If |vy| is odd, pump in once and the resulting string will have characters out of order. If it is even, pump
in once. The number of ab’s will no longer match the number of a’s in region 2 or b’s in region 3.
(2, 2) Pump in once. More a’s in region 2 than b’s in region 3.
(3, 3) Pump in once. More b’s in region 3 than a’s in region 2.
v or y crosses the boundary between 1 and 2: Pump in once. Even if v and y are arranged such that the
characters are not out of order, there will be more ab pairs than there are b’s in region 3.
(1, 3) |vxy| must be less than or equal to k.
c) {x#y : x, y Î {0, 1}* and x ¹ y}.
Context-free not regular. We can build a PDA M to accept L. All M has to do is to find one way in which x
and y differ. We sketch its construction: M starts by pushing a bottom of stack marker Z onto the stack.
Then it nondeterministically chooses to go to state 1 or 2. From state 1, it pushes the characters of x, then
starts popping the characters of y. It accepts if the two strings are of different lengths. From state 2, it must
accept if two equal length strings have at least one different character. So M starts pushing a % for each
character it sees. It nondeterministically chooses a character on which to stop. It remembers that character
in its state (so it branches and there are two similar branches from here on). It reads the characters up to the
# and does nothing with them. Starting with the first character after the #, it pops one % for each character
it reads. When the stack is empty it checks to see whether the next input character matches the remembered
character. If it does not, it accepts.
d) {aibn : i, n > 0 and i = n or i = 2n}.
Context-free, not regular. L can be generated by the following context-free grammar:
S ® A | B
A ® aAb | ab
B ® aaBb | aab
L is not regular, which we show by pumping: Let w = akbk. Pump out. To get a string in L, i must be equal
to n or greater than n (in the case where i =2n). Since we started with i = n and then decreased i, the resulting
string must not be in L.
e) {wx : |w| = 2×|x| and w Î a+b+ and x Î a+b+}.
Context-free, not regular. L can be accepted by a PDA M that pushes one character for each a and b in w
and then pops two characters for each a and b in x.
L is not regular, which we show by pumping. Note that the boundary between the w region and the x region
is fixed; it’s immediately after the last b in the first group. Choose to pump the string w = a2kb2kakbk. y =
Chapter 13 10
ap, for some nonzero p. Pump in or out. The length of w changes but the length of x does not. So the
resulting string is not in L.
f) {anbmck: n, m, k ³ 0 and m £ min(n, k)}.
Not context-free. We prove it using the Pumping Theorem. Let k be the constant from the Pumping Theorem
and let w = akbkck. Let region 1 contain all the a’s, region 2 contain all the b’s, and region 3 contain all the
c’s. If either v or y crosses numbered regions, pump in once. The resulting string will not be in L because it
will violate the form constraint. We consider the remaining cases for where nonempty v and y can occur:
(1, 1): Pump out once. This reduces the number of a’s and thus the min of the number of a’s and c’s. But
the number of b’s is unchanged so it is greater than that minimum.
(2, 2): Pump in once. The min of the number of a’s and c’s is unchanged. But the number of b’s is increased
and so it is greater than that minimum.
(3, 3): Same argument as (1, 1) but reduces the number of c’s.
(1, 2), (2, 3): Pump in once. The min of the number of a’s and c’s is unchanged. But the number of b’s is
increased and so it is greater than that minimum.
(1, 3): Not possible since |vxy| must be less than or equal to k.
g) {xyxR : x Î {0, 1}+ and y Î {0, 1}*}.
Regular. There is no reason to let x be more than one character. So all that is required is that the string have
at least two characters and the first and last must be the same. L = (0 (0 È 1)* 0) È (1 (0 È 1)* 1).
h) {xwxR : x, w Î {a, b}+ and |x| = |w|}.
Not context-free. If L were context-free, then L1 = L Ç a*b*a*ab*a* would also be context-free. But we
show that it is not by pumping. Let w =
ak+1 bk+1 ak+1 bk a bk+1 ak+1
1 | 2 3 | 4 | 5 6 | 7
We break w into regions as shown above. If either v or y from the pumping theorem crosses numbered
regions, pump in once. The resulting string will not be in L1 because it will violate the form constraint. If
either v or y includes region 5, pump in once and the resulting string will not be in L1 because it will violate
the form constraint. If |vy| is not divisible by 3, pump in once. The resulting string will not be able to be cut
into three pieces of equal length and so it is not in L1. We now consider the other ways in which nonempty
v and y could occur:
(1, 1), (2, 2), (1, 2): Pump in twice. One a and at least one b move into the last third of the string. So the
first third is apbq, for some p and q, while the last third is biajbk, for some i, j, and k. So the last third is not
the reverse of the first third.
(6. 6), (7, 7), (6, 7): Pump in twice. At least two a’s will move into the first third of the string. So the first
third is apbqar, for some p, q, and r, while the last third is ajbk, for some j and k. So the last third is not the
reverse of the first third.
(3, 3), (4, 4), (3, 4): Pump in twice. At least two a’s will move into the first third of the string and one a and
at least one b will move into the last third. So the first third is apbqar, for some p, q, and r, while the last
third is biajbk, for some i, j, and k. So the last third is not the reverse of the first third.
(2, 3): One a and at least one b will move into the last third of the string, so it will be biajbk, for some i, j,
and k. Depending on the length of v relative to the length of y, the first third will be either apbqar, for some
p, q, and r or apbq, for some p and q. In either case, the last third is not the reverse of the first third.
(4, 6): Pump in twice. At least two a’s will move into the first third of the string. So the first third is apbqar,
for some p, q, and r. Depending on the length of v relative to the length of y, the last third will be ajbk, for
some j and k or biajbk, for some i, j, and k. In either case, the last third is not the reverse of the first third.
All remaining cases are impossible since |vxy| must be less than or equal to k.
Chapter 13 11
3) Let L = {anbmcndm : n, m ³ 1}. L is interesting because of its similarity to a useful fragment of a typical
programming language in which one must declare procedures before they can be invoked. The procedure declarations
include a list of the formal parameters. So now imagine that the characters in an correspond to the formal parameter
list in the declaration of procedure 1. The characters in bm correspond to the formal parameter list in the declaration
of procedure 2. Then the characters in cn and dm correspond to the parameter lists in an invocation of procedure 1
and procedure 2 respectively, with the requirement that the number of parameters in the invocations match the number
of parameters in the declarations. Show that L is not context-free.
Not context-free. We prove it using the Pumping Theorem. Let w = ak bk ck dk.
1 | 2 | 3 | 4
If either v or y from the pumping theorem crosses numbered regions, pump in once. The resulting string will
not be in L because the letters will be out of order. We now consider the other ways in which nonempty v
and y could occur:
(1, 1), (3, 3) Pump in once. The a and c regions will no longer be of equal length.
(2, 2), (4, 4) Pump in once. The b and d regions will no longer be of equal length.
(1, 2), (3, 4), (2, 3) Pump in once. Neither the a and c regions nor the b and d regions will be of equal length.
(1, 3), (1, 4), (2, 4) Not possible since |vxy| £ k.
So L is not context-free.
6) Let L1 = L2 Ç L3.
a) Show values for L1, L2, and L3, such that L1 is context-free but neither L2 nor L3 is.
Let: L1 = {a
nbn : n ³ 0}.
L2 = {a
nbncj : j £ n}.
L3 = {a
nbncj : j = 0 or j > n}.
b) Show values for L1, L2, and L3, such that L2 is context-free but neither L1 nor L3 is.
Let: L2 = a*.
L1 = {a
n : n is prime}.
L3 = {a
n : n is prime}.
15) Let L1 = {anbm : n ³ m}. Let R1 = {(a È b)* : there is an odd number of a’s and an even number of b’s}. Use
the construction described in the book to build a PDA that accepts L1 Ç R1.
We start with M1 and M2, then build M3:
M1, which accepts L1 = ({1, 2}, {a, b}, {a}, D, 1, {2}), D = ((1, a, e), (1, a))
((1, b, a), (2, e))
((1, e, e), (2, e)
((2, b, a), (2, e)
((2, e, a), (2, e)
Chapter 13 12
M2, which accepts R1 = ({1, 2, 3, 4}, {a, b}, d, 1, {2}), d = (1, a, 2)
(1, b, 3)
(2, a, 1)
(2, b, 4)
(3, a, 4)
(3, b, 1)
(4, a, 3)
(4, b, 2)
M3, which accepts L1 Ç R1 = ({(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2,), (2, 3), (2, 4)}, {a, b}, {a}, D, (1,1),
{(2,2)}), D =
(((1, 1), a, e), ((1, 2), a))
(((1, 1), b, a), ((2, 3), e))
(((1, 2), a, e), ((1, 1), a))
(((1, 2), b, a), ((2, 4), e))
(((1, 3), a, e), ((1, 4), a))
(((1, 3), b, a), ((2, 1), e))
(((1, 4), a, e), ((1, 3), a))
(((1, 4), b, a), ((2, 2), e))
(((2, 1), b, a), ((2, 3), e))
(((2, 2), b, a), ((2, 4), e))
(((2, 3), b, a), ((2, 1), e))
(((2, 4), b, a), ((2, 2), e))
(((1, 1), e, e), ((2, 1), e))
(((1, 2), e, e), ((2, 2), e))
(((1, 3), e, e), ((2, 3), e))
(((1, 4), e, e), ((2, 4), e))
(((2, 1), e, a), ((2, 1), e))
(((2, 2), e, a), ((2, 2), e))
(((2, 3), e, a), ((2, 3), e))
(((2, 4), e, a), ((2, 4), e))
Appendix B 13
4 Decision Procedures for Context-Free Languages
1) Give a decision procedure to answer each of the following questions:
a) Given a regular expression a and a PDA M, is the language accepted by M a subset of the language generated
by a?
Observe that this is true iff L(M) Ç ¬L(a) = Æ. So the following procedure answers the question:
1. From a, build an FSM M* so that L(M*) = L(a).
2. From M*, build a new FSM M** so that L(M**) = ¬L(M*).
3. From M and M**, build a PDA M*** that accepts L(M) Ç L(M**)
4. If L(M***) is empty, return True, else return False.
b) Given a context-free grammar G and two strings s1 and s2, does G generate s1s2?
1. Convert G to Chomsky Normal Form.
2. Try all derivations in G of length up to 2|s1s2|. If any of them generates s1s2, return True, else return False.
c) Given a context-free grammar G, does G generate at least three strings?
To construct a decision procedure for this problem, we exploit the same idea that we used as the basis of the
Pumping Theorem. Let b be the branching factor of G and let n be the number of G’s nonterminals. Then
the longest string that G can generate and assign a parse tree with no duplicated nonterminals on any path
has length no more than bn. If G can generate even one string of length greater than that, then that string can
be pumped. So G generates an infinite number of strings and thus at least three. Further, if there is at least
one such long string, there must also be a shorter one (the result of pumping out from it). We also know that
|vxy| £ bn+1. So if G generates any string of length greater than bn +bn+1, then it must also generate at least
one whose length is between bn and bn+1 (because we can keep pumping out until we get such a shorter string).
So the following algorithm decides the question:
1. Examine G and determine b and n.
2. Set count to 0.
3. For every string w in SG* such that |w| £ bn do:
3.1. If decideCFL(G, w) then count = count + 1.
4. If count = 0 then return False.
5. If count ³ 3 then return True.
6. For every string w in SG* such that bn < |w| £ bn +bn+1 do:
6.1. If decideCFL(G, w) then return True.
7. Return False.
d) Given a context-free grammar G, does G generate any even length strings?
1. Use CFGtoPDAtopdown(G) to build a PDA P that accepts L(G).
2. Build an FSM E that accepts all even length strings over the alphabet SG.
3. Use intersectPDAandFSM(P, E) to build a PDA P* that accepts L(G) Ç L(E).
4. If decideCFLempty(P*) returns True then return False. Otherwise, return True.
e) Given a regular grammar G, is L(G) context-free?
1. Return True (since every regular language is context-free).