Non deterministic finite state automaton, Theory of Computation

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q0, Fi where Q, Σ, q0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}).

We must also modify the de?nitions of the directly computes relation and the path function to allow for the possibility that ε-transitions may occur anywhere in a computation or path. The ε-transition from state 1 to state 3 in the example, for instance, allows the automaton on input ‘a' to go from state 0 not only to state 1 but also to immediately go on to state 3. Similarly, it allows the automaton, when in state 1 with input ‘b', to move ?rst to state 3 and then take the ‘b' edge to state 0 or, when in state 0 with input ‘a', to move ?rst to state 2 and then take the ‘a' edge to state 3. Thus, on a given input ‘σ', the automaton can take any sequence of ε-transitions followed by exactly one σ-transition and then any sequence of ε-transitions. To capture this in the de?nition of δ we start by de?ning the function ε-Closure which, given a state, returns the set of all states reachable from it by any sequence of ε-transitions.

Posted Date: 3/21/2013 2:45:10 AM | Location : United States







Related Discussions:- Non deterministic finite state automaton, Assignment Help, Ask Question on Non deterministic finite state automaton, Get Answer, Expert's Help, Non deterministic finite state automaton Discussions

Write discussion on Non deterministic finite state automaton
Your posts are moderated
Related Questions
The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

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

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

Ask queyystion #Minimum 100 words accepted#

We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

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