Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 5
ADVERTISEMENT
1
2
3
4
5
6
7
8Exercises on pages 638-639 in Discrete mathematics and Its Ap-
plications
Exercise 4
Let G = ({S, A, B, a, b}, {a, b}, S, P ), where P consist of:
a) S → AB, A → ab, B → bb
b) S → AB, S → aA, A → a, B → ba
c) S → AB, S → AA, A → aB, A → ab, B → b
d) S → AA, S → B, A → aaA, A → aa, B → bB, B → b
e) S → AB, A → aAb, B → bBa, A → λ, B → λ.
Find the languages generated by G.
Solution
a) {abbb}
b) {aa, aba}
c) {abab, abb}
d) {a
}, where m ≥ 2, n ≥ 1
n
2m
, b
e) {a
}, where m, n ≥ 0
m
m
n
n
b
b
a
Exercise 7
Construct a derivation of 0
using the grammar G
(a) and G
(b) in Example 6.
2
4
1
1
2
Solution
a) S → 0S → 00S → 00S1 → 00S11 → 00S111 → 00S1111 → 001111.
b) S → 0S → 00S → 001A → 0011A → 00111A → 001111.
Exercise 8
Show that the grammars G
(a) and G
(b) in Example 6 generate the set {0
m
n
|m, n =
1
1
2
0, 1, 2, ...}.
Solution
a) m = 0, n = 0, S → λ
n
n
m = 0, n ≥ 1, S → S1 → ... → S1
→ 1
m
m
m ≥ 1, n = 0, S → 0S → ... → 0
S → 0
m
m
m
n
m
n
m ≥ 1, n ≥ 1, S → 0S → ... → 0
S → 0
S1 → ... → 0
→ 0
1
S1
b) m = 0, n = 0, S → λ
m = 0, n = 1, S → 1
n 1
n 1
n
m = 0, n ≥ 2, S → 1A → ... → 1
A → 1
1 → 1
m
m
m ≥ 1, n = 0, S → 0S → ... → 0
S → 0
m
m
m ≥ 1, n = 1, S → 0S → ... → 0
S → 0
1
5
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education