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
Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For


what are the advantages and disadvantages of wearable computers?

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

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


what exactly is this and how is it implemented and how to prove its correctness, completeness...

a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0. Since the le