[FOM] regular expressions

[Marcin Mostowski]

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