Automata Theory and Formal Languages

Automata theory and formal languages expose the relationship among a formal language, the machine model that recognizes it, and the expressive power obtained by adding memory. Definitions are kept compact and 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.

Finite-state transducers

Finite automata are commonly introduced as recognizers that accept or reject an input string. Some problems require more than recognition: the machine must produce an output sequence while consuming the input. A finite-memory model used this way is a finite-state transducer (FST).

recognizer:
input -> accept / reject

transducer:
input -> output

An FST can distinguish an input alphabet from an output alphabet. A transition may determine both the next state and the output symbol or string to emit. Moore and Mealy machines are useful special cases of this idea; the more general transducer view is convenient for staged transformations in text and speech processing.

A normalization rule, for example, may map one written sequence to a canonical representation:

consumed input: a b c
emitted output: x y

Applications can include spelling normalization, morphological processing, phoneme mapping, and controlled text preprocessing. Tokenization and vocabulary boundaries form a related but distinct layer, discussed in SentencePiece Tokenization, Normalization and Vocabulary Boundaries.

Transducers can also be composed. If the output of one transformation is the input of another, a pipeline can be viewed as:

input -> FST_1 -> intermediate form -> FST_2 -> output

Composition helps keep rules separate, but a finite-state model does not magically represent unlimited context. If a correct decision depends on arbitrarily long history or nested structure, finite memory may be insufficient. The first question is therefore whether the intended transformation is genuinely finite-state.

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.

Constructive equivalence and counterexample strategy

Equivalence claims in automata theory should be constructive whenever possible. To show that an NFA and a DFA recognize the same class of languages, subset construction gives an explicit DFA state for each reachable set of NFA states. To minimize a DFA, distinguishability partitions states according to whether some suffix can separate their future behavior.

Non-membership requires a different tool. The pumping lemma is not an algorithm for deciding regularity; it is a proof technique for showing that some languages cannot be regular. The proof must choose a sufficiently long string, quantify over every legal decomposition, and show that pumping produces a string outside the language.

Confusing these roles is a common source of invalid proofs.

Grammar transformations and parsing consequences

Context-free grammars can be transformed to forms such as Chomsky Normal Form when an algorithm requires a restricted production shape. The transformation must preserve the generated language apart from explicitly handled cases such as the empty string.

CYK parsing then uses dynamic programming over substrings and grammar variables. The algorithm makes the relation between grammar form, parsing complexity, and table structure explicit.

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.

Undecidability and Reductions

The Turing-machine model is useful not only for describing what can be computed, but also for expressing that some problems cannot be solved by any general algorithm.

Decidable and recognizable languages

A language is decidable if there is a Turing machine that halts on every input and returns the correct accept/reject decision. A machine may instead accept every string in the language while failing to halt on some strings outside the language; such a language can be recognizable without being decidable.

This distinction makes termination part of the computational contract rather than an implementation detail.

Reductions

Suppose an instance of problem A can be transformed computably into an instance of problem B, and a solver for B can then be used to obtain the answer to A.

instance of A
   ↓ computable transformation
instance of B
   ↓ solver for B
answer for A

Reductions are not only a design technique. If A is known to be unsolvable and A <= B can be established, then a general solver for B would imply a solver for A, producing a contradiction.

The halting problem

The halting problem asks whether one algorithm can decide, for every arbitrary program and input, whether that program eventually terminates. The classical result shows that no such general algorithm exists.

This does not mean that termination can never be proved. Restricted languages, particular program classes, and explicit formal proofs can establish termination. Undecidability concerns a solver that is required to handle all possible programs.

Intuition behind Rice's theorem

Any non-trivial semantic property of the function computed by an arbitrary program encounters a similar undecidability boundary when one asks for a universal decision procedure. The important distinction is between syntactic properties of program text and semantic properties of program behavior.

The formal-language perspective can be summarized as:

language class
   -> recognition power
   -> machine model
   -> decidability boundary

Being able to express a computation with an automaton does not imply that every meta-question about that computation is algorithmically decidable.

Designing a reduction

A reduction is an algorithmic transformation from instances of one problem to instances of another. To prove that problem B is at least as hard as problem A, the reduction must map every instance of A to an instance of B while preserving the yes/no answer.

The direction matters. Reducing an easy problem to a hard problem does not prove the easy problem hard.

For undecidability, the assumed decider for the target problem is used as a subroutine to decide a known undecidable problem, creating a contradiction. Rice's theorem generalizes this pattern for nontrivial semantic properties of the language recognized by a Turing machine.

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.

Where formal models meet real parsers

Regular and context-free languages explain the foundation of many tools, but real language processing includes additional concerns such as lexer state, indentation sensitivity, precedence, symbol tables, and semantic constraints.

Regular-expression engines also differ. Features such as backreferences go beyond classical regular languages, and some backtracking engines can exhibit exponential behavior for poorly designed patterns.

Parser quality includes diagnostics. A recognizer that only accepts or rejects may be theoretically sufficient, while a developer tool must report location, expected tokens, and useful recovery behavior.

How to test a formal-language claim

A few sample strings cannot prove that a language is regular or context-free. Positive claims require an appropriate construction such as an automaton, regular expression, grammar, or PDA; negative claims require formal tools such as pumping arguments, closure properties, or reductions.

Theory should also be separated from tool behavior. Backreferences and other features in practical regex engines can go beyond classical regular expressions, while parser generators may impose implementation constraints beyond the grammar class itself.

Small accept/reject test sets are useful for checking examples, but they do not replace proof. Examples test intuition; the formal argument carries the general claim.

From Formal Models to Artificial Intelligence

The connection between automata theory and AI is not merely historical. State, transition, symbol sequence, language, and computability remain useful abstractions in symbolic reasoning, planning, parsing, and reliable agent behavior. The connection is strongest when a formal model and a learned model are kept distinct rather than treated as interchangeable.

A finite automaton has an explicit state set and transition function:

q_(t+1) = δ(q_t, a_t)

The allowed transition is part of the model definition. In a learning system, a decision or transition function may instead be estimated from data. The two can also be composed. A perception model may classify an image or audio segment while a deterministic state machine governs which operational transitions are permitted.

This separation is valuable in autonomous and critical systems:

learned perception
↓
explicit state
↓
verifiable transition guard
↓
action

It avoids assigning every system responsibility to one opaque learned component.

Formal languages provide another durable connection. Regular expressions, finite-state transducers, context-free grammars, and parsers have long represented structural constraints in text and programming languages. Modern language models learn probabilistic patterns over symbol sequences, but a probability distribution over tokens does not guarantee that an output satisfies a required grammar. Grammar-constrained generation or post-validation can therefore provide a deterministic acceptance layer.

Search and planning also use the state-space view. If a problem can be represented by an initial state, valid actions, a transition model, and a goal condition, it becomes possible to search the induced graph. Classical AI methods such as A*, game-tree search, and planning extend this idea with costs and heuristics. The notion of state is not removed; the practical problem becomes deciding which transitions to explore in an enormous space.

Turing machines and computability establish a more fundamental boundary. A larger learned model does not make an uncomputable problem computable. AI systems still execute algorithms on physical computers and do not escape limits such as the halting problem. This distinction keeps improvements in empirical capability separate from theoretical computability.

Formal methods also provide a verification role around learned components. A model may propose a free-form output; a grammar, type system, state machine, or logical constraint can then check whether that output belongs to an acceptable set. The learned uncertainty remains, but the admissible output space becomes explicit.

Automata theory is therefore not a prerequisite theory for all of AI. Its more precise role is to provide exact models of state, language, transition, and computability, while AI methods use search, probability, and learning to operate in problem spaces that may be too large or uncertain for fully enumerated rules.

Read the language class from the machine model

In formal-language problems, the key question is not only whether a string is accepted but what kind of memory is required to recognise the language. A finite automaton has only finite-state memory and therefore cannot remember an arbitrarily large number of matched parentheses. A pushdown automaton adds a stack, making nested structure possible to track.

DFA and NFA are equivalent in expressive power: every NFA has an equivalent DFA accepting the same language. The difference lies in representation and potentially in the number of states. Regular expressions, regular grammars, and finite automata are likewise alternative descriptions of regular languages.

The pumping lemma is often used in the wrong direction. To prove that a language is regular, constructing a regular expression or finite automaton is usually more direct. The lemma is mainly useful for proving non-regularity by contradiction, and the adversarial order of choosing the decomposition must be respected.

For context-free grammars, derivations and parse trees are two views of the same generation process. If a string has more than one distinct parse tree, the grammar is ambiguous for that string. Grammar ambiguity does not automatically mean that the language itself is inherently ambiguous; another grammar may describe the same language without ambiguity.

At the Turing-machine level, recognisability and decidability must be distinguished. A recogniser may halt and accept members while running forever on some non-members. A decider must halt on every input. That boundary is central to computability theory.

References

• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson, 2006.

• Michael Sipser. Introduction to the Theory of Computation. Cengage, 2012.

• Peter Linz. An Introduction to Formal Languages and Automata. Jones & Bartlett Learning, 2011.

• Stuart Russell, P. N. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2021.