[FOM] regular expressions
pratt at cs.stanford.edu
Thu Nov 1 16:38:04 EDT 2007
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.)
More information about the FOM