Formal Language Theory: Automata and Grammars

Posted on Mar 18, 2026 in Commerce

Finite Automaton (FA) Fundamentals

A Finite Automaton (FA) is a mathematical model of computation used to recognize regular languages. It consists of a finite number of states and transitions between those states based on input symbols.

Formally, the FA is defined as:

FA = (Q, Σ, δ, q&剂;, F)

Where:

  • Q = finite set of states
  • Σ = input alphabet
  • δ = transition function
  • q&剂; = initial state
  • F = set of final (accepting) states

Deterministic Finite Automaton (DFA)

A Deterministic Finite Automaton (DFA) is a finite automaton in which each state has exactly one transition for each input symbol.

Characteristics:

  • No ε transitions
  • Only one possible next state

Example transition: δ(q0, a) → q1

Epsilon Non-Deterministic Finite Automaton (ε-NFA)

An ε-NFA (Epsilon Non-Deterministic Finite Automaton) is a type of NFA in which the automaton can change states without reading any input symbol. This transition is called an ε (epsilon) transition.

Definition:
An ε-NFA is a non-deterministic finite automaton that allows transitions on the empty string (ε).

Example transition: δ(q0, ε) → q1. This means the automaton can move from q0 to q1 without reading any input.

Key points:

  • Allows ε transitions
  • Multiple possible next states
  • Used to simplify construction of automata from regular expressions

Parse Trees and Derivation

A Parse Tree is a tree representation that shows how a string is derived from a grammar according to its production rules. It shows the syntactic structure of a string.

Features:

  • Root node = start symbol
  • Internal nodes = non-terminals
  • Leaf nodes = terminals

A Derivation Tree is another name for a Parse Tree. It represents the step-by-step derivation of a string from the start symbol using grammar rules.

Types of derivation:

  • Leftmost derivation
  • Rightmost derivation

Example Grammar: S → aSb | ab. String: aabb.

Context-Free Grammars (CFG)

A Context-Free Grammar is a grammar where the left side of every production rule has only one non-terminal symbol.

Form: A → α

Where:

  • A = single non-terminal
  • α = terminals and/or non-terminals

Example: S → aSb; S → ab

Chomsky Normal Form (CNF)

Chomsky Normal Form (CNF) is a special form of Context-Free Grammar (CFG) in which every production rule follows a simple and restricted structure.

In CNF, the production rules must be of the following forms:

  1. A → BC
  2. A → a

Where:

  • A, B, C are non-terminal symbols
  • a is a terminal symbol

So, in CNF: A variable can produce two variables, or A variable can produce one terminal symbol.

Example: S → AB; A → a; B → b

Pushdown Automaton (PDA)

A Pushdown Automaton (PDA) is a computational model similar to a finite automaton but with an additional stack memory.

A PDA is defined as:

PDA = (Q, Σ, Γ, δ, q&剂;, Z&剂;, F)

Where:

  • Q = states
  • Σ = input alphabet
  • Γ = stack alphabet
  • δ = transition function
  • q&剂; = initial state
  • Z&剂; = initial stack symbol
  • F = final states

PDA is used to recognize Context-Free Languages (CFL).

Example Language: anbn

Turing Machine (TM)

A Turing Machine is an automaton that has an infinite tape, a read–write head, and a finite set of states. It reads symbols from the tape, writes symbols on the tape, and moves the tape head left or right according to transition rules.

A Turing Machine is defined as:

TM = (Q, Σ, Γ, δ, q&剂;, B, F)

Where:

  • Q = finite set of states
  • Σ = input alphabet
  • Γ = tape alphabet
  • δ = transition function
  • q&剂; = initial state
  • B = blank symbol
  • F = set of final states