20 Aug 2001 01:44:17 -0400

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) |

From: | Vinay Kakade <kvinay@ip.eth.net> |

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

-Vinay Kakade.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.