[FOM] regular expressions

[Vaughan Pratt]

From: Adam Kolany
> Thanks again for answering my question.
> One little question:
> In the definition of A_L however, we use an infinite structure, which
> cannot be used in any algorithm.
> Can the automaton A_L be obtained in a more straigthforward way?

No, for all but a set of L's of measure zero.  There are uncountably 
many possible L's, but only countably many effective algorithms.

Depending on how L is presented, and what presentations of A_L are 
acceptable, there may exist an effective way of presenting the A_L 
associated with some effectively presented L.  A case in point is given 
by my Proposition 2 showing how to obtain A_L presented as a finite 
graph from L presented as a finite regular expression.  When L is 
presented as (the language generated by) a context-free grammar there is 
an algorithm for obtaining A_L presented as a nondeterministic pushdown 
automata.  (Presented directly as a graph, A_L is infinite when L is not 
regular, whence the need for a more sophisticated representation of A_L.)

Vaughan Pratt