Re:Making an NFA into a grammar

Hi,


>In Sec 4.3 of Compilers Principles, Techniques, and Tools, the authors
>give an algorithm for converting an NFA into a grammar that generates
>the same language as recognized by the NFA. Is there any algorithm,
>which when given a grammar, converts it back to an NFA, IFF the
>grammar represents a regular language. I know it is easy for grammars
>of the sort A -> a B since this is the kind of grammar which the above
>mentioned algorithm generates, but is there an algorithm that does
>this for the general case? Where the grammar productions might not be
>in the for A -> a B but the grammar represents a regular language?


According to my knowledge, a grammar for a regular language can be of
two types:


1. Right Linear Grammar:
This has productions of the form A -> aB and A -> b


2. Left Linear Grammar:
This has productions of the form A -> Ba and A -> b


Here is an alogorithm for conversion of a right linear grammar to FA.
(algorithm for conversion of a left linear grammar to FA will be
similar.)


Algorithm:
We construct an FA whose-
1. States correspond to non-terminals. In addition, there is also one
unique final state. (say F)
2. Initial state corresponds to start symbol of the grammar
3. Transitions correspond to productions in the grammar
(i) Each production A -> aB induces a transition from state A to state
B on
input a
(ii) Each production A -> b induces a transition from state A to state
F on
input a


-Vinay Kakade.

Return to the comp.compilers page.
Search the comp.compilers archives again.