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
how to find whether the language is cfl or not?

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

i want to do projects for theory of computation subject what topics should be best.

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

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

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

what are composition and its function of gastric juice

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p