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
Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

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

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.



State and Prove the Arden's theorem for Regular Expression

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi