Deterministic finite automata. Nondeterministic finite automata

Deterministic finite automata
Deterministic finite automaton (DFA) consists of three parts: a tape, a tape head (or, simply, head), and a finite control.

Deterministic finite automata

Deterministic finite automata
The tape head scans the tape, reads symbols from the tape, and passes the information to the finite control.

Deterministic finite automata
At each move of the DFA, the head scans one cell of the tape and reads the symbol in the cell, and then moves to the next cell to the right.

Deterministic finite automata

Deterministic finite automata
Then, it determines, from the current state and the symbol read by the tape, how the state is changed to a new state.

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata
When the DFA halts, it accepts the input string if it halts in one of the final states.
Otherwise, the input string is rejected.

Deterministic finite automata

Deterministic finite automata
The transition diagram of a DFA is an alternative way to represent the DFA.

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Deterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata
NFA’s, like DFA’s, can also be represented by transition diagrams.
In the transition diagram, we still use a vertex to represent a state and a labeled edge to represent a move, except that we allow multiple edges from one vertex to other vertices with the same label.

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata

Nondeterministic finite automata
Some of these computation paths lead to final states and some do not.

Nondeterministic finite automata