Finite Automata

Part II. Finite Automata

Different classes of automata exist; examples include finite automata and pushdown automata. Of these, the finite automaton is the simplest. In the Chomsky hierarchy, Type-3 (regular) languages are recognised by finite automata.

Formal definition and components

A finite automaton M is a 5-tuple

M = (Q, Σ, q₀, δ, F)

• Q is a finite set of states.
• Σ (sigma) is a finite set called the input alphabet (set of input symbols).
• q₀ ∈ Q is the start state (there is exactly one start state for the automata considered here).
• δ is the transition function that describes state changes on input symbols. Its precise type depends on whether the machine is deterministic or nondeterministic (explained below).
• F ⊆ Q is the set of final (accepting) states.

The following figure is an example of a finite automaton M:

For the automaton shown above, its components can be identified as follows.

• Q = { q₀, q₁, q₂, q₃, q₄ } - the set of states is shown as circles in the diagram.

• Σ = { a, b, c } - the input alphabet. Arrows (transitions) are labelled with these symbols.

• q₀ is the start state. A start state is usually indicated by an arrow coming from the empty space.

• δ describes the operation of the finite automaton. For a transition example,

δ(q₀, a) = q₁

This means: given the current state q₀ and the input symbol a, the automaton moves (transits) to state q₁.

Other example transitions (from the figure) are:

δ(q₁, b) = q₂

δ(q₂, c) = q₃

δ(q₁, c) = q₄

δ(q₃, b) = q₄

• F = { q₂, q₄ } - the set of final (accepting) states. Final states are commonly drawn with double circles.

Transition diagrams and transition tables

A finite automaton is often represented as a transition diagram, where states are nodes and transitions are labelled arrows. The same automaton can also be described by a transition table that lists, for every state and input symbol, the resulting state(s).

Notation used in diagrams or tables:

• → q₀ denotes that q₀ is the start state.
• ∗ q denotes that state q is a final (accepting) state. For example, a star before q₂ and q₄ indicates those are final states.

Language acceptability by a finite automaton

Informally, a finite automaton is used to check whether an input string is valid according to the rules encoded by its transitions. Formally, for a deterministic automaton the extended transition function δ* : Q × Σ* → Q maps a state and a string to the state reached after processing the entire string. For nondeterministic automata δ* maps to a set of states. A string w ∈ Σ* is accepted by M if the state(s) reached after processing w include at least one state from F. The language of M is L(M) = { w ∈ Σ* | M accepts w }.

String processing by a finite automaton - worked examples

Example 1:

Consider the following finite automaton M:

Check whether the string abcb is accepted by this automaton.

Processing begins at the start state q₀. Each line below shows the extended transition after reading the next symbol of the string.

δ(q₀, abcb) = q₁

δ(q₁, abcb) = q₂

δ(q₂, abcb) = q₃

δ(q₃, abcb) = q₄

After processing the whole string we end in q₄, which is a final state. Therefore the string abcb is accepted by M.

Example 2:

Consider the finite automaton M shown below:

Check whether the string abc is accepted by M.

Processing from the start state q₀:

δ(q₀, abc) = q₁

δ(q₁, abc) = q₂

δ(q₂, abc) = q₃

After processing all symbols the automaton halts at q₃. Since q₃ is not a final state, the string abc is rejected by M.

Example 3:

Consider the finite automaton M:

Check whether the string abca is accepted by M.

Processing from q₀:

δ(q₀, abca) = q₁

δ(q₁, abca) = q₂

δ(q₂, abca) = q₃

At this point we must process the final symbol a from state q₃, but there is no transition defined for (q₃, a).

Because the automaton cannot process the entire input string, the string abca is rejected by M.

Language of a finite automaton

Given a finite automaton M, its language L(M) consists of all strings accepted by M. For the automaton shown below:

Examples of membership in the language L(M):

• The string abcb belongs to L.
• The string abc does not belong to L.
• The string abca does not belong to L.
• The string ab belongs to L.
• The string ac belongs to L.
• The string abcbc does not belong to L.

Types of finite automata

Finite automata are classified mainly into two types:

• Non-deterministic Finite Automata (NFA)
• Deterministic Finite Automata (DFA)

Non-deterministic Finite Automata (NFA)

An NFA allows, from a given state and input symbol, multiple possible next states (or no next state). Thus the next move is not uniquely determined by the current state and the input symbol. Formally, for an NFA the transition function is

δ : Q × (Σ ∪ {ε}) → P(Q)

where P(Q) denotes the power set of Q and ε denotes the empty (epsilon) transition if epsilon transitions are present.

Example:

In the figure above, from state q₀ with input symbol 0 there are two possible next states: q₀ or q₁. From q₁ on input 1 the next state can be q₁ or q₂. Such nondeterministic choices characterise an NFA.

Example 1:

Consider the NFA below:

Check whether the string 0100 is accepted.

Processing along one possible path from the start state q₀:

δ(q₀, 0100) = q₀

δ(q₀, 0100) = q₀

δ(q₀, 0100) = q₃

δ(q₃, 0100) = q₄

Since q₄ is a final state, the string 0100 is accepted by the NFA (existence of at least one accepting path is sufficient).

Example 2:

Consider the NFA:

Check whether the string 01101 is accepted.

One possible sequence of moves is:

δ(q₀, 01101) = q₀

δ(q₀, 01101) = q₀

δ(q₀, 01101) = q₀

δ(q₀, 01101) = q₁

δ(q₁, 01101) = q₂

Since q₂ is final, the string 01101 is accepted.

Example 3:

Consider the NFA shown below:

Check whether the string abbaa is accepted.

One accepting path is:

δ(q₀, abbaa) = q₀

δ(q₀, abbaa) = q₀

δ(q₀, abbaa) = q₁

δ(q₁, abbaa) = q₂

δ(q₂, abbaa) = q_f

q_f is a final state, so abbaa is accepted.

NFA with epsilon (ε) transitions

An NFA may include transitions labelled with ε (epsilon). An ε-transition moves the automaton from one state to another without consuming any input symbol. Epsilon transitions allow the automaton to change state spontaneously. The ε-closure of a state is the set of states reachable from it by zero or more ε-transitions.

Example:

Check whether the string 100110 is accepted.

One sequence of moves:

δ(q₀, 100110) = q₀

δ(q₀, 100110) = q₀

δ(q₀, 100110) = q₀

δ(q₀, 100110) = q₁

δ(q₁, 100110) = q₂

δ(q₂, 100110) = q₂

δ(q₂, ε) = q₄

Since q₄ is final, the string 100110 is accepted. Note that the ε-move from q₂ to q₄ did not consume any input symbol.

Example 2:

Consider the NFA:

Check whether the string 0012 is accepted.

Processing along one path:

δ(q₀, 0012) = q₀

δ(q₀, 0012) = q₀

δ(q₀, ε) = q₁

δ(q₁, 0012) = q₁

δ(q₁, ε) = q₂

δ(q₂, 0012) = q₂

q₂ is final, so 0012 is accepted.

Deterministic Finite Automata (DFA)

A DFA is a finite automaton in which, for every state and every input symbol, there is exactly one defined next state and no ε-transitions. Formally,

δ : Q × Σ → Q

In a DFA, the next move is uniquely determined by the current state and the input symbol.

Example:

In the automaton above the input alphabet is {0, 1, 2}. From every state and for every symbol there is exactly one transition defined; hence the machine is deterministic. No ε transitions are present in a DFA.

Example 1:

The following transition diagram is a DFA:

The same DFA can be written as a transition table:

Check whether the string aaba is accepted.

Processing from the start state q₀:

δ(q₀, aaba) = q₀

δ(q₀, aaba) = q₀

δ(q₀, aaba) = q₁

δ(q₁, aaba) = q₁

After processing all symbols the automaton reaches q₁, which is a final state. Therefore aaba is accepted.

Example 2:

Consider the DFA shown below and check whether the string aabba is accepted.

One path of deterministic transitions yields:

δ(q₀, aabba) = q₀

δ(q₀, aabba) = q₀

δ(q₀, aabba) = q₁

δ(q₁, aabba) = q₀

δ(q₀, aabba) = q₀

After processing the whole string the automaton ends in q₀, which is not a final state. Thus aabba is rejected.

Important properties and remarks

• Equivalence: For every NFA (possibly with ε-transitions) there exists an equivalent DFA recognising the same language. The standard method to convert an NFA to a DFA is the subset construction (powerset construction).
• Expressive power: DFAs and NFAs recognise exactly the same class of languages: the class of regular languages (Type-3 languages).
• Decidability: Many problems for finite automata are decidable and have efficient algorithms, for example, testing whether a DFA accepts a given string is done in linear time in the string length.
• Applications: Finite automata are used in lexical analysis (token recognition), regular expression matching, network protocol design, hardware design (control circuits), and simple pattern matching tasks.

Summary

A finite automaton is a simple, yet powerful mathematical model for recognising regular languages. Its formal definition M = (Q, Σ, q₀, δ, F) captures the essential elements: states, input alphabet, start state, transition function and accepting states. Deterministic and nondeterministic variants are equivalent in expressive power, and both are fundamental tools in theory and practice for processing and recognising regular patterns.