Equivalence problem, Theory of Computation

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular languages. We will assume, yet again, that they are given as DFAs.

Theorem The Equivalence Problem for Regular Languages is decidable.

Posted Date: 3/21/2013 1:56:04 AM | Location : United States







Related Discussions:- Equivalence problem, Assignment Help, Ask Question on Equivalence problem, Get Answer, Expert's Help, Equivalence problem Discussions

Write discussion on Equivalence problem
Your posts are moderated
Related Questions
Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

how to prove he extended transition function is derived from part 2 and 3

how to convert a grammar into GNF

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

build a TM that enumerate even set of even length string over a

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular


what exactly is this and how is it implemented and how to prove its correctness, completeness...