[FOM] regular expressions
Marcin Mostowski
m.mostowski at uw.edu.pl
Tue Oct 30 21:41:04 EDT 2007
For both questions the answer is YES. Of course if a relation is decidable
then there is a formal system for proving it.
Decidability of equivalence of two regular languages (as given by any
recursively equivalent representation, e.g. finite automata, regular
expressions) can be obtained by easy argument: compute syntactical automata
for these two languages and compare them, if they are the same then the
languages are equal, otherwise they are different.
Adam Kolany napisał(a):
> 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?
> regards, Adam Kolany
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
_____________________
Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University
More information about the FOM
mailing list