Section 9.5 Formal Languages
797
13. Write the productions of the following grammars in BNF:
a. G in Exercise 2
b. G in Exercise 3
c. G in Exercise 4
14. Write the productions of the following grammars in BNF:
a. G in Exercise 10
b. G 3 in Example 58
15. A grammar G is described in BNF as
::= 1 0 1 0 00
a. Find a regular expression for L(G).
b. Find a regular grammar for L(G).
16. A grammar G is described in BNF as
::= 01 0 0 0 1
a. Find a regular expression for L(G).
b. Find a regular grammar for L(G).
17. Find a grammar that generates the set of all strings of well-balanced parentheses.
18. English words are translated into “pig latin” by the following two rules:
1. If a word begins with a vowel, add the suffix “yay”.
2. If a word begins with a string of one or more consonants, move the string of leading consonants to the
back of the word and then add the suffix “ay”.
a. What is the pig latin translation of the word “apple”?
b. What is the pig latin translation of the word “monkey”?
c. What is the pig latin translation of the word “chain”?
d. Find a grammar that generates all legal pig latin words.
e. Using your grammar from part d, generate the pig latin word that was the answer to part c.
19. A word w in V* is a palindrome if w = w
R
, where w
R
is the reverse of the string w. A language L is a
palindrome language if L consists entirely of palindromes. Find a grammar that generates the set of all
palindromes over the alphabet 5a, b6.
20. a. Let L be a palindrome language (see Exercise 19). Prove that L
R
= 5w
R
0 w [ L6 is a palindrome
language.
b. Let w be a palindrome. Prove that the language described by the regular expression w* is a palindrome
language.
21. Find a regular grammar that generates the language L = 11(0 ~ 1)*.
22. Find a regular grammar that generates the language L = (0 ~ 1)*01.
23. Find a grammar that generates the language L = 51
2n
0 n ≥ 06.
24. Find a regular expression for the language of Exercise 23. Is your grammar from Exercise 23 regular? If
not, write a regular grammar that generates L.
25. Find a context-free grammar that generates the language L = 50
n
1
n
0 n ≥ 06.
797
13. Write the productions of the following grammars in BNF:
a. G in Exercise 2
b. G in Exercise 3
c. G in Exercise 4
14. Write the productions of the following grammars in BNF:
a. G in Exercise 10
b. G 3 in Example 58
15. A grammar G is described in BNF as
a. Find a regular expression for L(G).
b. Find a regular grammar for L(G).
16. A grammar G is described in BNF as
a. Find a regular expression for L(G).
b. Find a regular grammar for L(G).
17. Find a grammar that generates the set of all strings of well-balanced parentheses.
18. English words are translated into “pig latin” by the following two rules:
1. If a word begins with a vowel, add the suffix “yay”.
2. If a word begins with a string of one or more consonants, move the string of leading consonants to the
back of the word and then add the suffix “ay”.
a. What is the pig latin translation of the word “apple”?
b. What is the pig latin translation of the word “monkey”?
c. What is the pig latin translation of the word “chain”?
d. Find a grammar that generates all legal pig latin words.
e. Using your grammar from part d, generate the pig latin word that was the answer to part c.
19. A word w in V* is a palindrome if w = w
R
, where w
R
is the reverse of the string w. A language L is a
palindrome language if L consists entirely of palindromes. Find a grammar that generates the set of all
palindromes over the alphabet 5a, b6.
20. a. Let L be a palindrome language (see Exercise 19). Prove that L
R
= 5w
R
0 w [ L6 is a palindrome
language.
b. Let w be a palindrome. Prove that the language described by the regular expression w* is a palindrome
language.
21. Find a regular grammar that generates the language L = 11(0 ~ 1)*.
22. Find a regular grammar that generates the language L = (0 ~ 1)*01.
23. Find a grammar that generates the language L = 51
2n
0 n ≥ 06.
24. Find a regular expression for the language of Exercise 23. Is your grammar from Exercise 23 regular? If
not, write a regular grammar that generates L.
25. Find a context-free grammar that generates the language L = 50
n
1
n
0 n ≥ 06.