# Re:Making an NFA into a grammar

## Vinay Kakade <kvinay@ip.eth.net>20 Aug 2001 01:44:17 -0400

From comp.compilers

Related articles
Re:Making an NFA into a grammar kvinay@ip.eth.net (Vinay Kakade) (2001-08-20)
Re: Re:Making an NFA into a grammar vannoord@let.rug.nl (2001-08-24)
| List of all articles for this month |

 From: Vinay Kakade Newsgroups: comp.compilers Date: 20 Aug 2001 01:44:17 -0400 Organization: Compilers Central Keywords: parse Posted-Date: 20 Aug 2001 01:44:17 EDT

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