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
Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine


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

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Can v find the given number is palindrome or not using turing machine

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

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

distinguish between histogram and historigram

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta