Regexps from DFA

G Venkatesha Murthy <gvmt@csa.iisc.ernet.in>
2 Feb 1997 21:28:22 -0500

          From comp.compilers

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)
| List of all articles for this month |

From: G Venkatesha Murthy <gvmt@csa.iisc.ernet.in>
Newsgroups: comp.compilers
Date: 2 Feb 1997 21:28:22 -0500
Organization: Compilers Central
Keywords: lex, question, comment

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


Post a followup to this message

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