[FOM] regular expressions
dr.a.kolany at wp.pl
Thu Nov 1 11:17:32 EDT 2007
Vaughan Pratt wrote:
> Adam Kolany wrote:
>> I am sorry for possibly trivial questions:
>> 1. Is the problem of equality of languages given by two regular
>> expresions equal decidable?
>> 2. Is there a (decidable) formal system for proving the above
>> For Proposition 1, take an infinite tree T all of whose vertices are of
>> out-degree the cardinality s of the alphabet S. All are of in-degree 1
>> save the root vertex which is of in-degree zero. There are no
>> leaves---all paths are infinite.
>> Label the s edges leaving each vertex of T with the respective s letters
>> of S.
>> Now associate to every vertex v of T the language w\L defined as the set
>> of those words x in S* such that wx is in L, where w is the word
>> labeling v per the above procedure. Call two vertices with labels v and
>> w *equivalent* when v\L = w\L, that is, when the two subtrees with
>> respective roots v and w are made equivalent automata by taking the
>> respective subtree's root to be the start state in each case. (The
>> final states remain marked as originally.)
>> One can show that the automaton obtained by identifying equivalent
>> vertices is the final automaton A_L in the category of all deterministic
>> automata accepting L. It has the further property that *any* automaton
>> accepting L can be turned into the final one by identifying states (the
>> sense in which it is final). This is crucial for the last stage of the
>> construction in Proposition 2.
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?
More information about the FOM