Regexps from DFA

Hi all,


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.


Venkatesha Murthy


--
                                        Venkatesha Murthy G.,
                        Department of Computer Science and Automation
                        Indian Institute of Science, Bangalore 560 012
                                                    INDIA


Res: IISc


57/1-A, Ratnavilasa Road Compilers Lab
Basavanagudi Phone 309 2368 Ext 215
Bangalore 560 004


WWW http://purana.csa.iisc.ernet.in/~gvmt
talk gvmt@yuga.csa.iisc.ernet.in
[I still don't understand the question. RE's are either valid or not,
and the alternation of a bunch of strings is as valid as any. You
turn it into a DFA and minimize it, and the pattern matcher you get is
the same size as the matcher from any other equivalent RE, no? -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.