Finite Automaton

automata-theory

Definition

Finite Automaton

A finite automaton is a Turing machine that does not use a work tape.

Its transitions therefore have the simple form

$$(q,a;p,D_E)$$

where $q,p$ are states, $a$ is the currently read input symbol, and $D_E\in \{R,S\}$ determines the movement of the input head.

If one allows only $D_E\in \{R,S\}$, the transition function can be written in the simpler form $(q,a;p)$ for $a\in T\cup \{\epsilon \}$. In this notation,

$$(q,a;p)\text{ for }a\in T$$

means $(q,a;p,R)$, and

$$(q,\epsilon ;p)$$

means $(q,a;p,S)$ for an arbitrary $a\in T$.

Convention

A finite automaton starts its computation on the first symbol of the input word. It accepts if it reaches an accepting state while the reading head stands on the right boundary symbol.