Week 1 - Nondeterminism

Question 1

What does it mean when a machine is deterministic?

Answer 1

When a machine is in a given state and reads the next input, it must have only one future state for that symbol that it can change to.

Question 2

What does it mean when a machine is nondeterministic?

Answer 2

When a machine is in a given state and reads the next input symbol, it may have zero, one or several choices for the next state to reach.

Question 3

What are the differences between a DFA and NFA?

Answer 3

Each state in a DFA has exactly one exiting transition arrow going to one state for each symbol of the alphabet and no other arrows. Whereas a state of an NFA can have one, none, or many exiting transition arrows each going to different states for one symbol of the alphabet.

Question 4

TRUE OR FASLE: A DFA counts as a NFA.

Answer 4

True.

Question 5

TRUE OR FASLE: A NFA counts as a DFA.

Answer 5

False.

Question 6

TRUE OR FALSE: Some transitions of an NFA can be labelled with an empty word Ɛ.

Answer 6

True.

Question 7

What counts as an accepted word/string in a NFA?

Answer 7

As long as at least one of the paths the process takes to execute the string it ends up in a final state at the end, then the word is accepted.

Question 8

When an NFA is executing and it comes accross a choice for the transition to take for an input what does it do?

Answer 8

The NFA copies itself and follows each path seperately.

Question 9

What happens if an NFA comes across a transition labelled with Ɛ during the process?

Answer 9

It moves through that transition to the next state without reading any more input.

Question 10

What happens during the process if a transition is labelled with both a symbol and Ɛ?

Answer 10

The process splits into two branching paths, following a path where the transition is for the symbol if that symbol was the one currently read in from the input, and a path that moves through the transition without reading any inputs.

Question 11

Define a Nondeterministic finite automaton (NFA) in compution terms.

Answer 11

An NFA is a tuple N = (Q, Σ, δ, q0, F) where
Q is a finite set of states.
Σ is a finite alphabet.
δ is a function Q x ΣƐ -> P(Q), where ΣƐ = Σ ⋃ {Ɛ}
q0∈Q is the initial state of the machine.
F⊆Q is the set of final states of the machine.

Question 12

How dod we define/write the language which is accepted by a NFA?

Answer 12

Assuming N is the NFA, w is a word, and Σ is the alphabet.

L = {w ∈ Σ* / N accepts w}