798
Modeling Arithmetic, Computation, and Languages
26. Find a context-free grammar that generates the language L = 5ww
R
0 w [ 50, 16* and w
R
is the reverse of
the string w}.
27. Find a context-free grammar that generates the language L where L consists of the set of all nonempty
strings of 0s and 1s with an equal number of 0s and 1s.
28. Find a context-free grammar that generates the language L where L consists of the set of all nonempty
strings of 0s and 1s with twice as many 0s as 1s.
29. Find a grammar that generates the language L = 50
2
i 0 i ≥ 06.
30. Find a grammar that generates the language L = 50
n
1
2n
0
n
0 n ≥ 06.
31. Find a grammar that generates the language L = 5ww 0 w [ 50, 16*6.
32. Find a grammar that generates the language L = 5a
n
2 0 n ≥ 16. (By Exercise 38, L is not a context-free
language, so your grammar cannot be too simple.)
33. Draw parse trees for the following words:
a. 111111 in the grammar G of Example 51
b. 111111 in the grammar G′ of Example 51
34. Draw parse trees for the following words:
a. 011101 in the grammar G of Exercise 2
b. 00111111 in the grammar G of Exercise 4
35. Consider the context-free grammar G = (V, V T , S, P) where V = 50, 1, A, S6, V T = 50, 16, and P
consists of
S S A1A
A S 0
A S A1A
Draw two distinct parse trees for the word 01010 in G. A grammar in which a word has more than one
parse tree is ambiguous.
36. Ambiguity in a grammar (see Exercise 35) that describes a programming language is an undesirable trait
because the compiler is unable to uniquely parse the programming instruction. Ambiguity in a natural
language can be similarly confusing. The following two instructions were posted beside an escalator.
“Shoes must be worn.”
“Dogs must be carried.”
Give two possible interpretations for each instruction.
37. Show that for any context-free grammar G there exists a context-free grammar G′ in which for every
production a S b, b is a longer string than a, L(G′) # L(G) and L(G) − L(G′) is a finite set.
38. Following is the pumping lemma for context-free languages. Let L be any context-free language. Then
there exists some constant k such that for any word w in L with 0 w0 ≥ k, w can be written as the string
w 1 w 2 w 3 w 4 w 5 with 0 w 2 w 3 w 4 0 ≤ k and 0 w 2 w 4 0 ≥ 1. Furthermore, the word w l w 2
i
w 3 w 4
i
w 5 [ L for each i ≥ 0.
a. Use the pumping lemma to show that L = 5a
n
b
n
c
n
0 n ≥ 16 is not context-free.
b. Use the pumping lemma to show that L = 5a
n
2 0 n ≥ 16 is not context-free.
Modeling Arithmetic, Computation, and Languages
26. Find a context-free grammar that generates the language L = 5ww
R
0 w [ 50, 16* and w
R
is the reverse of
the string w}.
27. Find a context-free grammar that generates the language L where L consists of the set of all nonempty
strings of 0s and 1s with an equal number of 0s and 1s.
28. Find a context-free grammar that generates the language L where L consists of the set of all nonempty
strings of 0s and 1s with twice as many 0s as 1s.
29. Find a grammar that generates the language L = 50
2
i 0 i ≥ 06.
30. Find a grammar that generates the language L = 50
n
1
2n
0
n
0 n ≥ 06.
31. Find a grammar that generates the language L = 5ww 0 w [ 50, 16*6.
32. Find a grammar that generates the language L = 5a
n
2 0 n ≥ 16. (By Exercise 38, L is not a context-free
language, so your grammar cannot be too simple.)
33. Draw parse trees for the following words:
a. 111111 in the grammar G of Example 51
b. 111111 in the grammar G′ of Example 51
34. Draw parse trees for the following words:
a. 011101 in the grammar G of Exercise 2
b. 00111111 in the grammar G of Exercise 4
35. Consider the context-free grammar G = (V, V T , S, P) where V = 50, 1, A, S6, V T = 50, 16, and P
consists of
S S A1A
A S 0
A S A1A
Draw two distinct parse trees for the word 01010 in G. A grammar in which a word has more than one
parse tree is ambiguous.
36. Ambiguity in a grammar (see Exercise 35) that describes a programming language is an undesirable trait
because the compiler is unable to uniquely parse the programming instruction. Ambiguity in a natural
language can be similarly confusing. The following two instructions were posted beside an escalator.
“Shoes must be worn.”
“Dogs must be carried.”
Give two possible interpretations for each instruction.
37. Show that for any context-free grammar G there exists a context-free grammar G′ in which for every
production a S b, b is a longer string than a, L(G′) # L(G) and L(G) − L(G′) is a finite set.
38. Following is the pumping lemma for context-free languages. Let L be any context-free language. Then
there exists some constant k such that for any word w in L with 0 w0 ≥ k, w can be written as the string
w 1 w 2 w 3 w 4 w 5 with 0 w 2 w 3 w 4 0 ≤ k and 0 w 2 w 4 0 ≥ 1. Furthermore, the word w l w 2
i
w 3 w 4
i
w 5 [ L for each i ≥ 0.
a. Use the pumping lemma to show that L = 5a
n
b
n
c
n
0 n ≥ 16 is not context-free.
b. Use the pumping lemma to show that L = 5a
n
2 0 n ≥ 16 is not context-free.