3 Feb 1997 13:46:39 -0500

Related articles |
---|

Regexps from DFA gvmt@csa.iisc.ernet.in (G Venkatesha Murthy) (1997-02-02) |

Re: Regexps from DFA anton@a0.complang.tuwien.ac.at (1997-02-03) |

Re: Regexps from DFA dimock@deas.harvard.edu (1997-02-03) |

Re: Regexps from DFA clark@quarry.zk3.dec.com (1997-02-07) |

Re: Regexps from DFA mslamm@pluto.mscc.huji.ac.il (1997-02-07) |

Re: Regexps from DFA lijnzaad@ebi.ac.uk (Philip Lijnzaad) (1997-02-07) |

From: | dimock@deas.harvard.edu (Allyn Dimock) |

Newsgroups: | comp.compilers |

Date: | 3 Feb 1997 13:46:39 -0500 |

Organization: | Aiken Computation Lab, Harvard University |

References: | 97-02-020 |

Keywords: | lex, DFA |

G Venkatesha Murthy <gvmt@csa.iisc.ernet.in> writes:

|> We recently had a post asking what regexp would describe a given set

|> of strings. Of course, there's the easiest one - one exact match for

|> each string - but we are interested in something "proper". I suppose

|> that answer lies in being able to extract a regexp from a DFA. How do

|> we get a regexp for a language accepted by a given DFA? Once we do

|> that, it is straight forward to obtain the regexp describing the set

|> of strings.

The idea of deriving a regular expression from a DFA is worth

reviewing.

Notice that the constructions used in proving the equivalence of

finita automata and regular espressions are constructive.

Lewis & Paparimitriou -- Elements of the theory of computation thm

2.5.1, example 2.5.2 pages 69 - 73

Hopcroft & Ullman -- Introduction to Automata Theory, Languages and

Computation Thm 2.4 and example 2.13 pages 33 - 35

Also see "Expression Automata" by J.A. Brzozowski, University of

Waterloo.

--------------------

Are the regular expressions generated byt these algorithms in any

sense "proper" I doubt it. The regular expressions that I have seen

generated by these algorithms are often simplifiable by standard

regular expression identities.

Is this process worthwhile? If you just go from a finite set of

strings to a NDFA by the standard construction and then immediately

apply Brzozowski's algorithm you end up with the union of the initial

strings plus the odd concatenation with the Kleene-* of the empty

string here and there.

If you create a NDFA, use the subset construction to convert to a DFA,

and minimize the DFA you end up (in worst case exponential time) with

a regular expression that is generally hard to read...

-- Allyn Dimock

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.