Constructing a NFA from a right linear grammar, is this correct?

4.1k Views Asked by At

Given the right linear grammar G

S -> abA | bbB  | a
A -> bB  | aA   | b
B -> baB | aaaA | [Epsilon/Terminates]

Is the NFA in the image below the proper construction of an NFA M(G) from the grammar?

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

That looks very good, and I think you certainly have the right idea. I see one minor mistake: I think the labels are switched on the two bottommost arrows labeled a and b. If I understand correctly, that accepting node represents strings that can be generated from $B$, and the two arrows below it represent the $B\to\mathtt{ba}B$ production, so the b arrow should come first on a path around the loop.

If I were doing this, I would label the $B$ node (the rightmost of the three accepting states) and the $A$ node (the node in the row second from right, with the loop) so that the grader will have an easy time seeing that your answer is correct.