Equivalence of nfas and dfas, Theory of Computation

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis as we have used in de?ning DFAs we shall see that to simulate an NFA one needs only track ?nitely much information about each string. Consider, again, the example in which we modeled the computation of the NFA as a set of automata processing the input synchronously. In order to determine if a string w is accepted by the NFA all we need to do is to track, at each stage of the computation (i.e., at each pre?x of the input), the states of those automata. Since there is never any reason to include more than one automaton for each state, this will just be some subset of Q-in fact, it is easy to see that the set of states after processing w will be just ˆ δ(q0,w). Since Q is ?nite, it has ?nitely many subsets. Thus we can simulate an NFA with state set Q with a DFA that has a state for each subset of Q. The process of constructing a deterministic analog of a non-deterministic machine is known as determinization.

Posted Date: 3/21/2013 2:55:40 AM | Location : United States







Related Discussions:- Equivalence of nfas and dfas, Assignment Help, Ask Question on Equivalence of nfas and dfas, Get Answer, Expert's Help, Equivalence of nfas and dfas Discussions

Write discussion on Equivalence of nfas and dfas
Your posts are moderated
Related Questions
A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

constract context free g ={ a^n b^m : m,n >=0 and n

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

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

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

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