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
When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

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

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn


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

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

shell script to print table in given range

constract context free g ={ a^n b^m : m,n >=0 and n

How useful is production function in production planning?