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
Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat


c program to convert dfa to re

Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

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