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
i have some questions in automata, can you please help me in solving in these 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

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

automata of atm machine

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

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.

The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive