Re: FW: Regular expressions / FSA question

From: Mitchell Harris (harris_at_tcs.inf.tu-dresden.de)
Date: 02/15/05 

Date: Tue, 15 Feb 2005 15:30:17 +0100

On Sun, 13 Feb 2005, someone wrote:

>Rather than post to a newsgroup, I sometimes write to people who have posted
>sensible replies and ask them my question. I have found this a more
>effective method for the level of questions I ask. When I do post, though
>not to comp.theory, it's more likely to be a reply. I got your email address
>from comp.theory

no problem. But since this is a question whose answer is probably
interesting to many others, I will anonymize it and post to comp.theory.

>As you doubtless know, there is a straightforward algorithm which takes as
>input a finite state automata (deterministic or non-deterministic) and
>produces a regular expression corresponding to the language accepted by the
>input.

Yes, the classic Kleene algorithm (or Floyd-Warshall-Kleene
(FWK) algorithm).

>Two questions:
>
>Have you heard of anyone implementing this as a computer program written in
>any standard language (say C, C++ or Java)?

certainly. heard of that is. Do I know of a url to get it? No. I would do
the same google keyword search that you would. my failing memory tells me
that a prof at Duke has some "teaching" apps that might do this.

OK, just looked:

  http://www.cs.duke.edu/~rodger/tools/jflap/

also there is the (non-teaching):

  http://odur.let.rug.nl/~vannoord/Fsa/

>It's fairly easy to design a machine with tape alphabet {0,1} which accepts
>only strings with an odd number of 1's and an even number of 0's. However
>the resulting regular expression is fairly disgustingly complex?

Oh, really? depends on what you mean by complex! Yes, if you use the FWK
algorithm (basically all pairs shortest paths but with the "weights" being
regular expressions, min = union, + = concatenation), you get a large
messy regular expression (again from memory). But you can do the
conversion by hand (that is without going through the bokkeeping insanity
of FWK), by taking the DFA and collapsing each vertex in turn, relabeling
the in, out, and to-self edges appropriately, until you're left with one
vertex (er, maybe two vertices, a start and a final, is necessary).

>Do you know of a regular expression for "odd 1's, even 0's"?

No, not off the top of my head, but heres's a start to the process:

1st the DFA

           0
     S <------ A
       ------>
     |^ 0 |^
    1||1 1||1
     || ||
     v| 0 v|
       <------
     B ------> C
      0

now remove node C ==>

           0
     S <------ A--\11
       ------> <-/
     |^ 0 |^
    1||1 ||
     || ||
     v| 10/|
       <-----/ /
     B ------/01
    | ^
    \-/
     00

and continue. You have to maintain the distinction between start and
finish here (I have not indicated the final state) because they are not
the same for this FA. If you have difficulty with this process I think it
is covered with a better example in Hopcroft, Ullman, and Motwani.

>I'm hoping to find the
>simplest such expression (to show to a class I teach).

As to -simplest- that's a whole nother story. The Myhill-Nerode thm gives
you the ("a") simplest (fewest nodes) -automaton-, but the simplest
-regular expression- is a different thing. Doing things by hand will tend
to be smaller in complexity because you'll maintain simplicity if only to
minimize writing, but thta's no gurantee. In other words, off the top of
my head I do not know of -the- simplest (shortest, I expect you mean)
regexp for it, and I have a feeling that that question is either
undecidable or of infeasible complexity (PSPACE or higher). (Any ideas?)
The names I would associate with this kind of work are Kozen or Pratt.

If you find out about this complexity, I would happy if you would relay
that info back to me. 

-- 
Mitch 
(remove the q to email)

Relevant Pages

  • Re: access database
    ... You could do this at various levels of complexity. ... even for departments within countries. ... Perhaps you should try the simplest form first and see what enhancements are ... SMTPAddress field. ...
    (microsoft.public.access.queries)
  • Re: Where is the error?
    ... But the way to make a sets position in the hierarchy ... extentional is to say that the complexity of a set S is the ... it the simplest. ... is the simplest form of f. ...
    (sci.logic)
  • Re: detect numeric value w/o regular expression
    ... What is the best and simplest ... way to do that without using regular expression or import other ... public static void main(Stringargs) { ...
    (comp.lang.java.programmer)
  • The elitists
    ... greatest complexity, can seldom accept even the simplest and most ... obvious truth if it be such as would oblige them to admit the falsity ...
    (sci.physics.relativity)
  • Leo sez
    ... greatest complexity, can seldom accept even the simplest and most ... obvious truth if it be such as would oblige them to admit the falsity ...
    (alt.gathering.rainbow)