17 Nov 2000 23:48:01 -0500

Related articles |
---|

Lex scanner cafelito@yahoo.com (Jorge) (2000-11-16) |

Re: Lex scanner vannoord@let.rug.nl (2000-11-17) |

Re: Lex scanner soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2000-11-17) |

From: | "Sönke Kannapinn" <soenke.kannapinn@wincor-nixdorf.com> |

Newsgroups: | comp.compilers |

Date: | 17 Nov 2000 23:48:01 -0500 |

Organization: | Siemens Inc. |

References: | 00-11-119 |

Keywords: | lex |

Posted-Date: | 17 Nov 2000 23:48:01 EST |

*> I'm doing some research in lexical scanners, and it was nice if*

*> someone can tell me any reference about algorithms that match if two*

*> regular expressions generate the same language.*

An obvious method using standard techniques is:

1. generate NFAs for both regular expressions

2. make DFAs out of the NFAs

3. minimize both DFAs; the result is unique up to isomorphism

4. check whether the two minimized DFAs are isomorphic

There are efficient algorithms for steps 1, 3, and 4. Step 2 is doomed to

have exponential worst-case complexity because the resulting DFA

(even the one with the minimal number of states) may have an exponential

number of states. However, that exponential complexity is unusual for

practical regular expressions.

I believe Aho/Sethi/Ullman's good old "dragon book" describes algorithms

for steps 1, 2, and 3.

Soenke.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.