Question

Let L be the language described by the following regular grammar: a. For each of the following strings, indicate whether it is a member of L: v. zyyzz b. Use grammartofsm (Rich 2008; page 157) to construct an FSM that accepts L c. Give a concise (but complete) description of L in plain English.

The grammartofsm algorithm:

Answer 1

a)

(i)-또 L (iii)yyy: 또 L (iv)zyyzz EL

b)

Explanation:

Step 1:

As per the algorithm, we will make 3 states for each S, U and T.

Step 2:

Make S as the starting state.

Step 3:

Productions U -> y and T -> z leads to the creation of # as the final state.

Step 4:

All the remaining productions are included in the FSM.

The resultant FSM is as follows:

c)

FSM accepts the language that starts and ends with the same symbol except z, y and epsilon.

Explanation:

If the string starts with z then it should end with z.

If the string starts with y then it should end with y.