Non-determinism - recognizable language, Theory of Computation

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 next state is fully determined by the current state and input symbol. As we saw in the previous section, this simpli?es the proof that the DFA accepts a speci?c language. There are many circumstances, though, in which it will be simpler to de?ne the automaton in the ?rst place if we allow for there to be any one of a number of next states or even no next state at all. Thus there may be many out edges from a given node labeled with a given symbol, or no out edges from that node for that symbol. Such FSA are called non-deterministic because the next step of a computation is not fully determined by the current state and input symbol-we may have a choice of states to move into.

De?nition 1 (NFA without ε-Transitions) A FSA A = (Q,Σ, T, q0, F) is non-deterministic iff either

• there is some q ∈ Q, σ ∈ Σ and p1 = p2 ∈ Q for which hq, p1, σi ∈ T and hq, p2, σi ∈ T,

• or there is some q ∈ Q, σ ∈ Σ for which there is no p ∈ Q such that hq, p, σi ∈ T

Posted Date: 3/21/2013 2:13:19 AM | Location : United States

Related Discussions:- Non-determinism - recognizable language, Assignment Help, Ask Question on Non-determinism - recognizable language, Get Answer, Expert's Help, Non-determinism - recognizable language Discussions

Write discussion on Non-determinism - recognizable language
Your posts are moderated
Related Questions
Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

What is the purpose of GDTR?

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

turing machine for prime numbers

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

matlab v matlab