3. Finite automata basics

Finite automata basics

A theoretical model for programs using a constant amount of memory regardless of the input form.

Finite control device

Finite control device: in any moment, it can be in one of its states, it is hard-wired in how it changes from one state to another. There are also some special states, such as one initial state and possible more favourable states.

• Has a reading head.
• It reads from an input tape: divided into cells, having a leftmost cell, each cell contains one character of the input alphabet and is fed into the machine.

Link to original

Starting finite automation

• The finite control device is put in its unique initial state.

• The tape contains a finite word of the input alphabet, the input, as its left end. The remainder of the tape contains only blank cells.

• The reading head is positioned on the leftmost cell of the input tape, containing the first character of the input word.

  $$\begin{array}{l}\downarrow \text{reading head}\\ \begin{array}{ccccccccc}a& b& c& b& b& a& \text{textvisiblespace}& \text{textvisiblespace}& ...\end{array}\end{array}$$

How it works

At regular time intervals, the automaton:

• reads one character from the input tape
• moves the reading head one cell to the right, and
• chooses the next state of its control device

The control device is hard-wired such that the next state depends on:

1. the previous state
2. the character read from the tape

As the input is finite, at some moment the reading head reaches the end of the input word (the first blank cell). If at this moment the control device is in a favourable state, then the input word is accepted by the automaton. Otherwise, the input word is not accepted, rejected.

Used for

• Each finite automaton is a kind of ‘recognition’ or ‘decision’ device over all possible words of its input alphabet.

• Each automaton can be ‘tried’ on infinitely many input words, and gives a Y/N answer each time.

  $$\begin{array}{rl}abbbbaba& \to \boxed{A}\to \text{YES}\\ aba& \to \boxed{A}\to \text{NO}\\ ϵ& \to \boxed{A}\to \text{YES}\\ \text{...}& \to \boxed{A}\to \text{...}\end{array}$$