Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 6
ADVERTISEMENT
1
2
3
4
5
6
7
8m
m
m
n 1
m
n 1
m
n
m ≥ 1, n ≥ 2, S → 0S → ... → 0
S → 0
1A → ... → 0
A → 0
1 → 0
1
1
1
Exercise 11
Find a phrase-structure grammar for each of the following languages.
Solution
a) G = ({0, 1, S}, {0, 1}, S, P ), where P consist of S → 00S, S → λ
b) G = ({0, 1, S, A, B}, {0, 1}, S, P ), where P consist of S → 1A, A → 0B, B → 00B,
B → λ
d) G = ({0, 1, S, A}, {0, 1}, S, P ), where P consist of S → 0000000000A, A → 0A|λ
Exercise 14
Find a context-free grammar that generates the set of all palindromes over the alphabet {0, 1}
Solution
G = ({0, 1, S}, {0, 1}, S, P ), where P consist of S → 0S0, S → 1S1, S → 0, S → 1, S → λ.
Exercise 15
Let G
and G
be context-free grammars. generating the language L(G
) and L(G
) respec-
1
2
1
2
tively. Show that there is a context-free grammar generating each of the following sets:
a) L(G
) ∪ L(G
)
1
2
b) L(G
)L(G
)
1
2
c) L(G
)
∗
1
Solution
Let G
) and
= ({w
}, {w
}, S
, ..., w
, S
, A
, ..., A
, ..., w
, P
1
1
k
1
1
m
1
k
1
1
}, {q
}, S
= ({q
).
G
, ..., q
, S
, B
, ..., B
, ..., q
, P
k
m
k
2
1
2
1
1
2
2
a) Grammar G
, that generates the set L(G
), is
) ∪ L(G
3
1
2
}, {q
}, S, P
∪
G
= ({q
, ..., q
, w
, ..., w
, S, S
, S
, A
, ..., A
, B
, ..., B
, ..., q
, w
, ..., w
k
k
m
m
k
k
3
1
1
1
2
1
1
1
1
1
∪ (S → S
|S
)).
P
2
1
2
b) Grammar G
, that generates the set L(G
), is
)L(G
3
1
2
= ({q
}, {q
}, S, P
∪
G
, ..., q
, w
, ..., w
, S, S
, S
, A
, ..., A
, B
, ..., B
, ..., q
, w
, ..., w
3
1
k
1
k
1
2
1
m
1
m
1
k
1
k
1
∪ (S → S
)).
P
S
2
1
2
c) Grammar G
, that generates the set L(G
, is
)
∗
3
1
}, {w
}, S, P
∪ (S → λ|S
G
= ({w
, ..., w
, S, S
, A
, ..., A
, ..., w
S)).
3
1
k
1
1
m
1
k
1
1
6
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education