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 universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}


The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

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