[FOM] regular expressions
Andrej.Bauer at fmf.uni-lj.si
Tue Oct 30 21:19:06 EDT 2007
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
The standard reference for this sort of thing, and more, is
"The Theory of Parsing, Translation, and Compiling" by Alfred V. Aho and
Jeffrey D. Ullman, 1972 Prentice-Hall. There are newer editions, if I am
You could also just look at Wikipedia first to see that this can be
done, http://en.wikipedia.org/wiki/Regular_expression, although I do not
see a _specific_ reference on that page that would confirm the claim
that it can be done.
More information about the FOM