Automata Theory and Formal Languages

I originally kept these notes to see the relationship among a formal language, the machine model that recognizes it, and the expressive power obtained by adding memory. I have kept the definitions compact and the transformations procedural. The progression from regular languages to Turing machines remains the organizing idea.

Unit 1: Finite Automata

Finite-automaton model

A finite automaton is an abstract machine with a finite set of states. It reads an input string symbol by symbol and changes state according to a transition function. Its memory is therefore limited to the current state.

A deterministic finite automaton can be written as:

M = (Q, Sigma, delta, q0, F)

where:

• Q is a finite set of states,
• Sigma is the input alphabet,
• delta: Q x Sigma -> Q is the transition function,
• q0 is the initial state,
• F is the set of accepting states.

Alphabet, symbol and string

An alphabet is a finite non-empty set of symbols. A string is a finite sequence of symbols from an alphabet. epsilon denotes the empty string.

If:

Sigma = {0, 1}

then 0101 is a string over Sigma. Sigma* denotes the set of all finite strings over the alphabet, including epsilon.

Language

A formal language over Sigma is any subset of Sigma*:

L subseteq Sigma*

The central question is not whether the strings look meaningful to a human but whether they satisfy a formally stated membership rule.

Deterministic finite automata

In a DFA, every state has exactly one next state for each input symbol. For example, a machine that accepts binary strings ending in 01 can keep only enough state to remember the relevant suffix.

The extended transition function applies delta to a complete string:

delta*(q, epsilon) = q

delta*(q, wa) = delta(delta*(q, w), a)

A string w is accepted when:

delta*(q0, w) in F

Transition diagrams and tables

A transition diagram represents states as nodes and transitions as labeled directed edges. The same machine can be represented by a table in which rows are states and columns are input symbols. The two representations carry the same information; one is often better for visual reasoning, the other for systematic construction.

Nondeterministic finite automata

An NFA allows several possible next states for the same state/symbol pair:

delta: Q x Sigma -> P(Q)

A string is accepted if at least one possible computation path ends in an accepting state after the input is consumed.

Nondeterminism changes the description style but not the class of languages recognized by finite automata. Every NFA has an equivalent DFA, although the DFA can require exponentially more states in the worst case.

Epsilon transitions

An epsilon-NFA may change state without consuming an input symbol. An epsilon transition does not add expressive power beyond regular languages; it makes constructions and regular-expression conversion more convenient.

The epsilon closure of a state is the set of states reachable using zero or more epsilon transitions. Subset construction for an epsilon-NFA begins from the epsilon closure of the start state and applies symbol transitions followed by closure.

NFA to DFA conversion

Subset construction represents each DFA state as a set of NFA states:

1. start with the NFA start state or its epsilon closure,
2. for each input symbol, compute all reachable NFA states,
3. treat that set as one DFA state,
4. repeat until no new sets appear,
5. mark a DFA state accepting when its set contains at least one accepting NFA state.

This construction proves DFA/NFA equivalence.

Two-way finite automata

A two-way finite automaton can move its input head in both directions on a read-only input. Despite the additional movement, the standard finite-state version still recognizes only regular languages. Its control can be more succinct, but finite control does not create unbounded memory.

Instantaneous description

An instantaneous description records the current configuration of a machine. For a finite automaton this usually means the current state plus the unread portion or current position in the input. More powerful models add stack or tape contents to the configuration.

Moore and Mealy machines

A Moore machine associates output with states. A Mealy machine associates output with transitions.

For a Moore machine:

output = lambda(state)

For a Mealy machine:

output = lambda(state, input)

Mealy outputs can react immediately to an input transition and may require fewer states. Moore outputs are tied to stable states and can be simpler to reason about in synchronous designs. Equivalent behavior can often be converted from one representation to the other, though output timing conventions must be handled carefully.

Automaton minimization

DFA minimization removes unreachable states and merges states that are behaviorally equivalent. Two states are equivalent if no continuation string can distinguish them with respect to acceptance.

A standard partition-refinement process begins by separating accepting and non-accepting states, then repeatedly splits groups when their outgoing transitions lead to distinguishable groups. The final partition defines the states of a minimal DFA, unique up to renaming.

Unit 2: Regular Languages and Regular Expressions

Regular languages

A language is regular if it is recognized by a finite automaton. Equivalent descriptions include:

• DFA,
• NFA,
• epsilon-NFA,
• regular expression,
• regular grammar.

This equivalence is one of the central results of introductory automata theory.

Regular expressions

Regular expressions are formed from basic languages using union, concatenation and Kleene star.

For alphabet symbols a and b:

a|b
ab
a*

represent union, concatenation and zero-or-more repetition. Parentheses control grouping. Concatenation normally binds more strongly than union; star applies to the immediately preceding expression or group.

Kleene star

For language L:

L* = union over n >= 0 of L^n

and therefore always contains epsilon. L+ is commonly used for one-or-more repetition:

L+ = L L*

when that notation is available.

Regular expression to automaton

Thompson-style construction builds an epsilon-NFA recursively:

• a symbol becomes a small fragment,
• union joins alternatives with epsilon branches,
• concatenation connects fragments,
• star adds epsilon paths for zero repetitions and repetition.

The resulting epsilon-NFA can then be converted to a DFA and minimized if needed.

Automaton to regular expression

A finite automaton can be converted back to a regular expression through state elimination or by solving regular-language equations. Arden's lemma is useful in equation-based derivations. In one common form, if:

X = A X union B

and epsilon is not in A, then:

X = A* B

under the corresponding orientation conventions.

Closure properties

Regular languages are closed under operations including:

• union,
• intersection,
• complement,
• difference,
• concatenation,
• Kleene star,
• reversal.

Intersection can be constructed with a product automaton. Complement for a complete DFA is obtained by swapping accepting and non-accepting states.

Pumping lemma

The pumping lemma gives a necessary property of every regular language. If L is regular, there exists a pumping length p such that sufficiently long strings in L can be decomposed:

w = xyz

with constraints typically including:

|xy| <= p
|y| > 0
xy^i z in L for all i >= 0

To prove a language non-regular, assume it is regular, choose a carefully structured string of length at least p, consider every legal decomposition, and show that some pumping choice leaves the language.

The lemma is primarily a non-regularity tool. Fulfilling a pumping-style condition in a few examples does not prove regularity.

Myhill-Nerode view

Two prefixes are indistinguishable with respect to L if every continuation either causes both resulting strings to belong to L or both not to belong to L. A language is regular exactly when this equivalence relation has finitely many classes. These classes correspond to the states of the minimal DFA.

This result explains minimization more deeply than a mechanical table procedure: a DFA state represents a distinct future behavior class.

Unit 3: Grammars and Languages

Grammar

A formal grammar can be described as:

G = (V, Sigma, P, S)

where:

• V contains variables/nonterminals,
• Sigma contains terminals,
• P is the production set,
• S is the start symbol.

Productions describe how strings containing nonterminals may be rewritten.

Derivation

A derivation repeatedly applies productions from the start symbol until a terminal string is obtained. A leftmost derivation always expands the leftmost nonterminal first; a rightmost derivation expands the rightmost one. The language generated by a grammar is the set of all terminal strings derivable from its start symbol.

Chomsky hierarchy

The traditional hierarchy distinguishes:

• Type 3: regular grammars,
• Type 2: context-free grammars,
• Type 1: context-sensitive grammars,
• Type 0: unrestricted grammars.

Their expressive power increases as production restrictions are relaxed. The corresponding machine models move from finite automata through pushdown-like and linearly bounded models to Turing-complete computation.

Regular grammars

Right-linear or left-linear regular grammars correspond to finite automata. A right-linear production typically has forms such as:

A -> aB
A -> a
A -> epsilon

subject to the chosen formal definition.

Converting a right-linear grammar to an automaton maps nonterminals to states and productions to transitions. The reverse conversion builds productions from automaton transitions.

The key limitation is memory: regular descriptions cannot count or match arbitrarily nested structure requiring unbounded memory.

Unit 4: Context-Free Grammars

Context-free grammar

A context-free production has a single nonterminal on the left:

A -> alpha

where alpha may contain terminals and nonterminals.

A classic language is:

L = { a^n b^n | n >= 0 }

which can be generated by:

S -> aSb | epsilon

A finite automaton cannot in general remember an unbounded number of a symbols to match against the number of b symbols; a pushdown store can.

Parse trees

A parse tree represents the hierarchical structure of a derivation. The root is the start symbol, internal nodes correspond to nonterminals expanded by productions, and leaves form the terminal string.

Ambiguity

A grammar is ambiguous if at least one string has more than one distinct parse tree, equivalently more than one distinct leftmost or rightmost derivation. Expression grammars often become ambiguous when precedence and associativity are not encoded explicitly.

For arithmetic, separate grammar levels for expressions, terms and factors can encode conventional precedence rather than relying on parser-side guesses.

Recursion

Recursive productions represent repeated or nested structures. Left recursion such as:

E -> E + T | T

is natural for some bottom-up parsers but problematic for naive recursive-descent parsing. Equivalent grammar transformations can remove immediate left recursion when needed.

Nullable variables, unit productions and useless symbols

Grammar simplification can remove:

• nullable productions in controlled form,
• unit productions such as A -> B,
• symbols that cannot derive terminal strings,
• symbols that are not reachable from the start symbol.

Simplification should preserve the intended language, with special care for epsilon when it belongs to the language.

Chomsky normal form

In CNF, productions are normally restricted to forms such as:

A -> BC
A -> a

with a controlled exception for the start symbol deriving epsilon when required. CNF is useful for proofs and algorithms such as CYK rather than because it is a convenient human grammar format.

Greibach normal form

In GNF, productions begin with a terminal followed by zero or more nonterminals:

A -> a alpha

It is useful in theoretical arguments about derivation structure and pushdown automata.

CYK algorithm

CYK determines whether a string belongs to a language generated by a grammar in CNF. It fills a dynamic-programming table for substrings, beginning with length-one terminal matches and combining smaller spans according to binary productions.

The classical complexity is cubic in input length for a fixed grammar:

O(n^3)

with grammar-dependent factors.

Pumping lemma for context-free languages

Context-free languages have a pumping property involving a decomposition commonly written:

w = uvxyz

with bounded middle region and both v and y pumped together. As with the regular pumping lemma, this is mainly a tool for proving that a language is not context-free; it is not a general membership test.

Unit 5: Pushdown Automata

PDA model

A pushdown automaton extends finite control with a stack. A typical formal description includes states, input alphabet, stack alphabet, transition relation, initial state and initial stack symbol.

The stack gives unbounded LIFO memory. That is sufficient for many nested structures and for the standard class of context-free languages.

Instantaneous description

A PDA configuration records at least:

(current state, unread input, stack contents)

A transition may consume an input symbol or epsilon, inspect the stack top, and replace it with zero or more stack symbols.

Acceptance

PDAs can be defined to accept by final state or by empty stack. For nondeterministic PDAs, these acceptance modes are equivalent in expressive power with suitable constructions.

Palindrome-style example

For a language with a visible middle marker, a PDA can:

1. push symbols from the first half,
2. detect the middle marker,
3. pop while matching the second half,
4. accept when both input and required stack content are exhausted.

Without a middle marker, a nondeterministic PDA can guess the midpoint. A deterministic PDA cannot recognize every context-free language, so deterministic and nondeterministic PDAs differ in expressive power even though DFA and NFA do not.

CFG and PDA equivalence

For every context-free grammar there is a nondeterministic PDA recognizing the same language, and for every nondeterministic PDA there is an equivalent context-free grammar. The constructions formalize the equivalence between context-free derivation and stack-based recognition.

Unit 6: Turing Machines

Basic model

A Turing machine combines finite control with an unbounded tape divided into cells. A transition depends on the current state and tape symbol and can:

• write a symbol,
• move the head left or right,
• enter a new state.

A standard transition function may be written conceptually as:

delta(q, a) = (q', b, D)

where D is the head direction.

Recognizable and decidable languages

A Turing machine recognizes a language if it accepts exactly the strings in the language; it may loop forever on some strings outside the language.

A language is decidable if some Turing machine halts on every input and accepts exactly the members of the language.

Thus every decidable language is recognizable, but not every recognizable language is decidable.

Example: matching several counts

A Turing machine can recognize languages such as:

{ a^n b^n c^n | n >= 0 }

by repeatedly marking one a, one corresponding b, and one corresponding c, then returning to repeat the process. This language is not context-free, illustrating the additional power supplied by general tape memory.

Variants

Multi-tape Turing machines, nondeterministic Turing machines and other conventional variants do not increase the class of Turing-computable functions. They can change description convenience or simulation efficiency, but the standard computability class remains the same.

Universal Turing machine

A universal Turing machine accepts an encoding of another machine together with its input and simulates that computation. This is the theoretical foundation for the idea of a stored program interpreted by a general machine, although practical computer architecture is not literally a Turing-machine implementation.

Church-Turing thesis

The Church-Turing thesis states, informally, that every effectively computable function can be computed by a Turing-equivalent formal model. It is a thesis connecting an intuitive notion of effective computation to formal models, not a theorem proved from a purely mathematical definition of "effective".

Halting problem

The halting problem asks whether an arbitrary program/machine halts on a given input. There is no Turing machine that correctly decides this for every possible machine/input pair.

The standard diagonal argument assumes such a decider exists and constructs a machine whose behavior contradicts the decider's prediction when applied to its own encoding. The result establishes a fundamental limit of general program analysis.

Hierarchy and machine power

A useful correspondence is:

Regular language        <-> finite automaton
Context-free language   <-> nondeterministic pushdown automaton
Recursively enumerable  <-> Turing machine recognizer
Decidable language      <-> halting Turing machine decider

Each extra memory model supports structures that cannot generally be represented by the weaker one.

Unit 7: Parsing

Lexical and syntactic analysis

A compiler commonly separates lexical analysis from parsing. The lexer maps character sequences to tokens; the parser checks whether the token sequence conforms to a grammar and constructs structural information.

A parse tree contains grammar-oriented detail. An abstract syntax tree normally removes grammar-only nodes and preserves the semantic structure needed by later compiler phases.

Top-down parsing

Top-down parsing begins from the start symbol and predicts productions that can derive the input. Recursive-descent parsers implement grammar procedures directly in code.

Naive recursive descent cannot handle immediate left recursion such as:

E -> E + T | T

because the procedure can recurse without consuming input. A standard transformation introduces a helper nonterminal:

E  -> T E'
E' -> + T E' | epsilon

Left factoring extracts common prefixes so that a parser can choose a production with limited lookahead.

FIRST and FOLLOW

FIRST(alpha) contains terminals that can begin strings derived from alpha, and may include epsilon when alpha can derive the empty string.

FOLLOW(A) contains terminals that can appear immediately to the right of nonterminal A in some sentential form, plus the end marker for the start symbol according to the usual construction.

These sets are used to construct predictive parsing tables.

LL(k) and LL(1)

LL(k) means scanning input left to right, producing a leftmost derivation, with up to k symbols of lookahead. An LL(1) parser uses one lookahead token.

For an LL(1) grammar, each parsing-table cell must lead to at most one production. FIRST/FIRST and relevant FIRST/FOLLOW conflicts indicate that the grammar is not LL(1) in its present form.

Bottom-up parsing

Bottom-up parsing starts from the input and reduces substrings toward the start symbol. Shift-reduce parsing alternates between:

• shifting an input symbol/token onto a stack,
• reducing a recognized handle according to a production.

A handle is a substring corresponding to one step of the reverse of a rightmost derivation.

LR parsing

LR parsers read left to right and reconstruct a rightmost derivation in reverse. LR items record how much of a production has been seen. closure expands items for nonterminals expected next; GOTO computes transitions between item sets.

An LR(0) item can be written:

A -> alpha . beta

The dot marks the parser position. LR(1) items additionally carry one-symbol lookahead information, allowing more precise reduction decisions.

The generated automaton and ACTION/GOTO tables drive a stack-based parse loop. A shift-reduce conflict means the parser cannot decide whether to shift or reduce in a state/lookahead situation. A reduce-reduce conflict means two reductions are simultaneously possible.

Common families include LR(0), SLR, canonical LR(1) and LALR. They trade table size, construction complexity and grammar coverage.

LL and LR comparison

LL parsing predicts a production before consuming its right-hand side and naturally matches hand-written recursive descent. LR parsing recognizes handles after seeing enough input and accepts a larger class of deterministic context-free grammars.

The choice is an engineering decision involving grammar shape, diagnostics, tooling and implementation complexity rather than a universal ranking.

Connection to compilers

A simplified compiler front end is:

characters
   ↓ lexer
 tokens
   ↓ parser
 syntax structure
   ↓ semantic analysis
 typed/interpreted intermediate form

Automata theory therefore connects directly to practical lexical analyzers, parsers, protocol recognizers and validation systems.

Fundamental Equivalences Between the Topics

Regular languages

The following descriptions are equivalent in expressive power:

regular expression
regular grammar
DFA
NFA
epsilon-NFA

They describe regular languages.

Context-free languages

Context-free grammars and nondeterministic pushdown automata describe the context-free level. Their stack memory allows unbounded nesting that finite automata cannot generally recognize.

General computability

Turing machines provide the standard model of general effective computation. Their significance is not that practical computers look like one-tape machines, but that a broad range of reasonable computation models can simulate one another at the computability level.

Memory and language power

The progression can be summarized as:

finite state
    ↓ add a stack
pushdown memory
    ↓ add general read/write tape
Turing-complete memory

The important lesson is that recognition power is tied to the form of memory available to the machine. Regular expressions, grammars and automata are therefore not isolated topics; they are alternative descriptions of computational capability at different levels.