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
Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

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

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

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

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