1.2 nondeterminism

  • Determinism(DFA) is a subset of nondeterminism(NFA).
  • For each letter in DFA, it could only be on only one arrow.
  • NFA may have on the arrow,means one or many arrows may exit from this state(zero).
  • If a string in a branch is accepted, then NFA accepts the input string.

Formal Def of NFA

A nondeterministic finite automation is a 5-tuple(), where:

  • is a Finite set of states
  • is a finite alphabet
  • is the transition function
  • is the start state
  • is the set of accept states

Formal Def of computation for an NFA:

Let N=() be an NFA and a string over the alphabet . Then we say that N asscepts if we can write as , where each is a member of and a sequence of states exists in with the following three conditions:

Equivalence of NFAs & DFAs

Two machines are equivalent if they recognize the same language.

Every nondeterministic finite automation has an equivalent deterministic finite automation.