1.2 NONDETERMINISM (briðgeng stöðuvél)

Question 1

In a nondeterministic machine

Answer 1

Several choices may exist for the next state at any point

Question 2

Nondeterminism is a generalization of determinism, so

Answer 2

every deterministic finite automaton is automatically a nondeterministic finite automaton.

Question 3

The difference between a deterministic finite automaton, abbreviated DFA, and a nondeterministic finite automaton, abbreviated NFA

Answer 3

First, every state of a DFA always has exactly one exiting transition arrow for each symbol in the alphabet. The NFA violates that rule.

Second, in a DFA, labels on the transition arrows are symbols from the alpha- bet. This NFA has an arrow with the label ε. In general, an NFA may have arrows labeled with members of the alphabet or ε.

Question 4

How does an NFA compute?

Answer 4

Suppose that we are running an NFA on an input string and come to a state with multiple ways to proceed. After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallel. Each copy of the machine takes one of the possible ways to proceed and continues as before. If there are subsequent choices, the machine splits again. If the next input symbol doesn’t appear on any of the arrows exiting the state occupied by a copy of the machine, that copy of the machine dies, along with the branch of the computation associated with it. Finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA accepts the input string.

Question 5

As we will show, every NFA can be converted into an equivalent DFA, and constructing NFAs is sometimes easier than directly constructing DFAs.

Question 6

The formal definition of a nondeterministic finite automaton is similar to that of a deterministic finite automaton. Both have states, an input alphabet, a transition function, a start state, and a collection of accept states. However, they differ in one essential way:

Answer 6

in the type of transition function.

In an NFA, the transition function takes a state and an input symbol or the empty string and produces the set of possible next states.

Question 7

A nondeterministic finite automaton is a 5-tuple (Q,Σ,δ,q0,F), where

Answer 7

1. Q is a finite set of states,
2. Σ is a finite alphabet,
3. δ : Q × Σε −→ P (Q) is the transition function,
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.

Question 8

Every nondeterministic finite automaton has an equivalent deterministic finite
automaton.

Question 9

If k is the number of states of the NFA, it has 2^k subsets of states. Each subset corresponds to one of the possibilities that the DFA must remember, so the DFA simulating the NFA will have how many states ?

Answer 9

2^k states.

Question 10

A language is regular if and only if some nondeterministic finite automaton recognizes it.