Looking for a Unsorted Math Worksheet Templates? Download it for free!

Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 4

Figure 2. FA M 1

Solution

1. Select a non-terminal for each state in M

, selecting a start symbol for the initial state: S for

, A for q

and B for q

2. Add productions corresponding to all transitions: S → 0S for q

, S → 1A for q

→ q

A → 0S for q

, A → 1B and A → 1 for q

, B → 1B and B → 1 for q

, and

→ q

B → 0B and B → 0 for q

, since q

is an accepting state.

→ q

G = ({0, 1, S, A, B}, {0, 1}, S, P ), where P is:

S → 1A|0S

A → 1B|0S|1

B → 0B|1B|0|1

Exercise 2 on slide 20

Argue why L(M ) = L(G) for the regular grammar G constructed from M in the proof sketch

above.

Solution

See Exercise 2 on slide 19.

Exercise 3 on slide 20

Argue that any FA M is equivalent to a NFA where the initial state has no incoming transition.

Solution

Any FA M has an equivalent NFA M where the initial state has no incoming transitions, if:

(a) this M was made from M by adding a new initial state q

instead of the old one q

, where

remains in the M

(b) and the same outgoing transitions as q

has, were added to q

Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 4