Automata Theory is a branch of computer science that studies abstract self-propelled computing devices that automatically follow a predetermined sequence of operations. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

What is an Automaton?

The term "Automata" is derived from the Greek word αὐτόματα, meaning "self-acting." An automaton is an abstract computing device that follows a predetermined sequence of operations automatically.

Formal Definition

A Finite Automaton is represented by a 5-tuple (Q, ∑, δ, q0, F), where:

Key Terminologies

Alphabet

A finite set of symbols.

Example: ∑ = {a, b, c, d} is an alphabet set where a, b, c, d are symbols.

String

A finite sequence of symbols taken from ∑.

Example: 'cabcad' is a valid string on the alphabet ∑ = {a, b, c, d}

Length of a String

The number of symbols in a string, denoted |S|.

• •If S = 'cabcad', then |S| = 6
• •If |S| = 0, it is an empty string, denoted by λ or ε

Kleene Star (∑*)

A unary operator that gives the infinite set of all possible strings of all possible lengths over ∑, including λ.

Representation: ∑* = ∑⁰ ∪ ∑¹ ∪ ∑² ∪ …

Example: If ∑ = {a, b}, then ∑* = {λ, a, b, aa, ab, ba, bb, …}

Kleene Closure / Plus (∑+)

The infinite set of all possible strings over ∑, excluding λ.

Representation: ∑+ = ∑¹ ∪ ∑² ∪ ∑³ ∪ … = ∑* − {λ}

Example: If ∑ = {a, b}, then ∑+ = {a, b, aa, ab, ba, bb, …}

Language

A subset of ∑* for some alphabet ∑. It can be finite or infinite.

Example: If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = {ab, aa, ba, bb}

Types of Finite Automaton

Finite Automata are classified into two types:

• •Deterministic Finite Automaton (DFA)
• •Non-deterministic Finite Automaton (NDFA / NFA)

Deterministic Finite Automaton (DFA)

In a DFA, for each input symbol, the machine moves to exactly one determined state. As it has a finite number of states, it is called a Deterministic Finite Machine.

Formal Definition

A DFA is represented by a 5-tuple (Q, ∑, δ, q0, F) where:

Graphical Representation

A DFA is represented as a state diagram (digraph) where:

• •Vertices represent the states
• •Labeled arcs show the transitions on input symbols
• •An empty single incoming arc denotes the initial state
• •Double circles indicate final states

Example

Given a DFA where Q = {a, b, c}, ∑ = {0, 1}, q0 = {a}, F = {c}:

State a is the initial state. State c is the final state.

Non-deterministic Finite Automaton (NDFA)

In an NDFA, for a particular input symbol, the machine can move to any combination of states. The exact next state cannot be predetermined.

Formal Definition

An NDFA is represented by a 5-tuple (Q, ∑, δ, q0, F) where:

Note: The transition function maps to 2^Q (the power set of Q), because from a single state, the machine can transition to any combination of states.

Example

Given an NDFA where Q = {a, b, c}, ∑ = {0, 1}, q0 = {a}, F = {c}:

State a is the initial state. State c is the final state.

DFA vs NDFA

Read Also: Lexical Analysis - How Compilers Use Finite Automata

Acceptors, Classifiers, and Transducers

Transducers come in two forms:

• •Mealy Machine: output depends on both the current state and current input
• •Moore Machine: output depends only on the current state

Acceptability by DFA and NDFA

A string S is accepted by a DFA/NDFA if and only if starting from the initial state q0, the machine ends in an accepting state after reading the entire string.

Formally:

• •Accepted: δ*(q0, S) ∈ F
• •Rejected: δ*(q0, S) ∉ F

NDFA to DFA Conversion

Every NDFA has an equivalent DFA. The conversion creates a DFA whose states represent subsets of NDFA states.

Algorithm

Input: NDFA represented as X = (Qx, ∑, δx, q0, Fx)

Output: Equivalent DFA represented as Y = (Qy, ∑, δy, q0, Fy)

1. •Create a state table from the given NDFA
2. •Create a blank DFA state table for all possible input alphabets
3. •Mark the DFA start state as q0 (same as NDFA)
4. •For each DFA state, compute the set of NDFA states reachable under each input symbol
5. •Repeat step 4 for every newly generated DFA state
6. •Any DFA state containing an NDFA final state becomes a final state in the DFA

Example

NDFA transition table:

Equivalent DFA transition table:

DFA Minimization

Method 1: Myhill-Nerode Theorem

Removes redundant states by finding pairs of states that are indistinguishable.

Input: DFA

Output: Minimized DFA

1. •Draw a table for all pairs of states (Qi, Qj), all initially unmarked
2. •Mark pair (Qi, Qj) if one is a final state and the other is not
3. •Repeat: mark (Qi, Qj) if {δ(Qi, A), δ(Qj, A)} is already marked for any input symbol A
4. •Combine all remaining unmarked pairs into single states

Example

Step 1: All pairs unmarked

Step 2: Mark pairs where one state is final, the other is not

Step 3: Mark transitively

Inputting 1 to states a and f leads to c and f. Since (c, f) is already marked, we mark (a, f). Inputting 1 to states b and f leads to d and f. Since (d, f) is already marked, we mark (b, f).

Result: Unmarked pairs: {a, b}, {c, d}, {c, e}, {d, e}

Recombining {c, d}, {c, e}, {d, e} gives {c, d, e}

Minimized DFA states: {f}, {a, b}, {c, d, e}

Method 2: Equivalence Theorem

Two states X and Y can be combined into {X, Y} if they are not distinguishable. Two states are distinguishable if there exists a string S where exactly one of δ(X, S) and δ(Y, S) is accepting.

Algorithm:

1. •Divide all states Q into two partitions: final states and non-final states (P0). Set counter k = 0.
2. •Increment k. For each partition in Pk, split states that are k-distinguishable (i.e., differ on some input after k−1 steps)
3. •If Pk ≠ Pk−1, repeat step 2; otherwise go to step 4
4. •Combine kth equivalent sets into new states of the reduced DFA

Example

Input DFA:

Applying the algorithm:

Since P1 = P2, we stop. Three states in the reduced DFA:

Reduced DFA:

Moore and Mealy Machines

Finite automata that produce output on each transition are called transducers. There are two types:

Mealy Machine

Output depends on both the current state and the current input.

Formal definition: 6-tuple (Q, ∑, O, δ, X, q0)

State table (state a is the initial state):

Moore Machine

Output depends only on the current state.

Formal definition: 6-tuple (Q, ∑, O, δ, X, q0)

State table (state a is the initial state):

Mealy vs Moore Machine

Moore Machine to Mealy Machine Conversion

Input: Moore Machine

Output: Mealy Machine

1. •Take a blank Mealy Machine transition table
2. •Copy all Moore Machine transition states into the table
3. •For each state Qi with output m in the Moore table, copy m into the output column of every row in the Mealy table where Qi appears as a next state

Example

Input Moore Machine (state a is the initial state):

Steps 1 and 2: Copy transitions into blank Mealy table

Step 3: Fill outputs from Moore table

For each next state, copy the output of that state from the Moore table: d has output 1, b has output 0, a has output 1, c has output 0.

Mealy Machine to Moore Machine Conversion

Input: Mealy Machine

Output: Moore Machine

1. •Count distinct outputs for each state Qi in the Mealy table
2. •If all outputs from Qi are the same, keep it as one state. If there are n distinct outputs, split Qi into n states (Qi0, Qi1, …)
3. •If the output of the initial state is 1, insert a new initial state that outputs 0

Example

Input Mealy Machine (state a is the initial state):

Analysis:

• •State a: outputs 0 and 1 - as a next state it always arrives with the same output, so it stays as a
• •State d: always output 0, stays as d
• •State b: outputs 1 and 0, split into b0 and b1
• •State c: outputs 1 and 0, split into c0 and c1

Resulting Moore Machine: