Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 3
ADVERTISEMENT
1
2
3
4
5
6
7
8a,b
a,b
a
qS
qT
qacc
a,b
b
qU
Figure 1. NFA N
for grammar G
1
1
Exercise 1 on slide 19
Construct a NFA N
from the grammar G
slide 6: G
= ({a, b, S, T, U }, {a, b}, S, P ), where
1
1
1
P is:
S → a|b|aT |aU |bT |bU
T → a
U → b
Solution
1. Create a state for each non-terminal and add a single accepting state q
.
acc
2. Add transitions q
for S → aT , q
for S → aU , q
for S → bT , q
a
a
b
b
→ q
→ q
→ q
→ q
S
T
S
U
S
T
S
U
for S → bU , q
for S → a, q
for S → b, q
for T → a, q
for
a
b
a
b
→ q
→ q
→ q
→ q
S
acc
S
acc
T
acc
U
acc
U → b (See Figure 1.)
Exercise 2 on slide 19
Argue why L(G
) = L(N
).
1
1
Solution
To prove that L(G
), let us define all words that leads to a final state in N
which is
) = L(N
1
1
1
)(1), and all words that can be generated in G
which is L(G
)(2):
L(N
1
1
1
(1) L(N
) = {w : w is concatenated symbols from the transitions in a path from start state to a
1
final state}
(2) L(G
) = {w : w is concatenated symbols from the productions in a path from start symbol
1
to a terminal}.
Since each transition in N
corresponds to a certain production from G
, and transitions are
1
1
connected by the states that correspond to certain non-terminals, which connect corresponding
productions, L(G
) = L(N
).
1
1
For this particular example L(G
) = {a, b, ab, bb, aa, ba} = L(N
).
1
1
Exercise 1 on slide 20
Construct a regular grammar from the FA M
(See Figure 2.) on slide 4 from the lecture about
1
FA.
3
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education