4.1Introduction to Finite Automata

Our plan is to start with a very concrete example of a finite automaton in the form of tally counters, learn how to do computation with it, and then generalize.

4.1.1(Simple) tally counters¶

Consider the modest tally counters that you have probably seen at entrances to bars, concerts, museums, and other venues where they are used to keep track of how many people have entered and how many have left.

The tally counter has 3 components:

1. A displayed number that is initially 0000, and can go up to 9999. We call this number the count.

2. An “increment” button on top. Pressing the button increments the number by 1 if the current count is less than 9999, and it becomes 0000 otherwise, i.e. it adds 1 modulo 10000.

3. A “reset” dial on the right side. The dial can be used to reset the count to 0000 by rotating it clockwise sufficiently many times.

Thus, we can view the tally counter as a device with 10000 states, whose initial state is 0, and that receives as input a sequence of “increments” and “resets”.^[1]

4.1.2(Even simpler) single-digit tally counter¶

To make the rest of our discussion manageable, in the remainder, we focus on the state of the first digit (i.e. the rightmost digit). This is equivalent to a single-digit tally counter that operates as follows:

1. It has 10 states, corresponding to the numbers $0, ..., 9$.

2. Its initial state is 0.

3. Let $i$ be the current state.

   • Incrementing changes its state to $i \mod 10$.

   • Resetting changes its state to 0.

We can succinctly represent the single-digit tally counter using a state transition table and a state diagram.

State transition table:

State diagram:

4.1.3Turning counters into computational devices¶

Let’s now turn the single-digit tally counter into a computational device that receives its input bit string as a sequence of bits, one bit at a time. There are two tasks we need to turn it into a finite automaton:

1. Specify how the device accepts/rejects strings.^[2] In general, this is done by indicating some states as accepting states and defining an input string to be accepted if the device ends up in an accepting state at the end of the string.

2. Specify how it transitions between states in response to each incoming bit of the input. In particular, we need to specify a state transition table.

Let us keep things simple and suppose that the string is accepted if the final state of the tally counter is 0. Consider the following simple examples, and let’s see what the set of accepted strings are in each of these examples.

Let’s take a look at its state transition table and diagram

For this one, it can be helpful to take a look at this Ed lesson which simulates the finite automaton.

In general, from any state, we can go to any other state by using a sequence of “increments”.

4.1.4Finite automata for bit strings¶

Recall the state transition table for Exercise 1 the first example above.

In general, we can define a finite automaton for bit strings using a state transition table with 3 columns:

• Each row represents a state of the finite automaton

• Column 1: name of the state

• Column 2: which state to transition to if next bit is 0

• Column 3: which state to transition to if next bit is 1

Here’s the formal definition of finite automata for bit strings.

4.1.5Finite automata in general¶

In general, we can have strings with other “alphabets”, depending on the application.

Let $M$ be a finite automaton. Consider an input string $w = v_1 v_2 \cdots v_n$ where each $v_i$ is a symbol of the alphabet. The finite automaton processes $w$ as follows:

1. Start at the start state

2. For each input symbol $v_i$ (starting from $v_1$), follow the corresponding transition: if the current state is $q$, then go to state $\delta(q,v_i)$.

3. After all input symbols have been processed, it accepts the string if the final state (also called the resulting state) is an accepting state, and rejects it otherwise.

In particular, it goes through the following sequence of state transitions:

where we use the notation $r_{i-1} \xrightarrow{v_{i-1}} r_i$ to mean that $r_i = \delta(r_{i-1}, v_i)$, i.e. the state after processing the $i$-th symbol of the input string $w$.

The final state $r_n$ is called the resulting state of $w$. We define the notation $q(w)$ to mean the resulting state of $w$.

4.1.6Computation path¶

The state transition diagram representation gives a nice graphical representation of the sequence of state transitions that a finite automaton $M$ goes through while processing a string $w$. In particular, we can represent the sequence

as a path in the state transition diagram that starts from $r_0$ (the initial state), goes to $r_1$, then $r_2$, and so on. Note that the path can repeat vertices.^[3]

We refer to this path as the computation path of $M$ on input $w$.

4.1.7Key features of a finite automaton¶

1. Constant memory

   • Memory = states and number of states is independent of input length

   • (Memorylessness) Behavior depends only on current state and next symbol, e.g. it does not remember how many times it has visited the current state before

2. Receive the input as a stream

   • (It ain’t over till it’s over) Does not know when the input is going to end

Observe that the tally counter has the above properties. Clearly, its memory is fixed and cannot allocate new memory.

Analogous to a program that has two phases:

1. (Initialisation phase) Before seeing the input, it declares the set of variables, and the set of possible values they can take. This includes a variable called IsAccept which can be either True or False.

2. (Input processing phase) While the stream is not empty, get next symbol and update variables. No new variables can be declared. Variables restricted to values declared in Init phase.

3. (Final phase) When stream is empty, return IsAccept