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
Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

build a TM that enumerate even set of even length string over a

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

how to find whether the language is cfl or not?

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

how many pendulum swings will it take to walk across the classroom?

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

how to understand DFA ?

What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?