# 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.