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
The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

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

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

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

turing machine for prime numbers

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

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. 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 sec

Describe the architecture of interface agency

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}