Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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.
Return to the
comp.compilers page.
Search the
comp.compilers archives again.