Equivalence of nfas, Theory of Computation

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via a path that includes some number of ε-transitions (before the σ-transition, after it or both), we can get the same effect by extending the transition relation to include a σ-transition directly from q to v. So, in the example we could add ‘a' edges from 0 to 1 (accounting for the path 0 2072_Equivalence of NFAs.png 3) and from 1 to 3 (accounting for the path 1 27_Equivalence of NFAs1.png 3) and ‘b' edges from 1 to 3 (accounting for the path 1 1649_Equivalence of NFAs2.png  3), from 3 to 2 (accounting for the path 3 1088_Equivalence of NFAs3.png2), and from 1 to 2 (accounting for the  path 1 2144_Equivalence of NFAs4.png2), Note that in each of these cases this corresponds to extending δ(q, σ) to include all states in ˆ δ(q, σ). The remaining effect of the ε-transition from 0 to 2 is the fact that the automaton accepts ‘ε'. This can be obtained, of course, by simply adding 0 to F. Formalizing this  we get a lemma.

Posted Date: 3/21/2013 2:54:59 AM | Location : United States







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

Write discussion on Equivalence of nfas
Your posts are moderated
Related Questions
how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

what problems are tackled under numerical integration


We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima