Regexps from DFA

G Venkatesha Murthy <>
2 Feb 1997 21:28:22 -0500

          From comp.compilers

Related articles
Regexps from DFA (G Venkatesha Murthy) (1997-02-02)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (Philip Lijnzaad) (1997-02-07)
| List of all articles for this month |

From: G Venkatesha Murthy <>
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

Res: IISc

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

[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.