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

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

write short notes on decidable and solvable problem

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

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

draw pda for l={an,bm,an/m,n>=0} n is in superscript

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

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

write short notes on decidable and solvable problem

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