Deterministic finite automata. Nondeterministic finite automata

1.

Finite automata
Irina Prosvirnina
• Deterministic finite automata
• Nondeterministic finite automata

2.

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

3.

Deterministic finite automata
The tape is used to store the input data. It is divided
into a finite number of cells. Each cell holds a symbol
from a given alphabet Σ.

4.

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

5.

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.

6.

Deterministic finite automata
The finite control has a finite number of states which
form the state set