[FOM] regular expressions

[Andrej Bauer]

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
> equalities?

1. Yes.
2. Yes.

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
not mistaken.

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.

Best regards,

Andrej