12. Formal Languages and Automata
12.1 Generative Grammars and the Chomsky Hierarchy
An alphabet is a finite nonempty set of symbols. A word or string over alphabet
Concatenation joins words. If
For words, Also define:
| Concept | Meaning |
|---|---|
| Subword | |
| Proper subword | |
| Prefix | |
| Suffix | |
| Mirror image | The word obtained by reversing symbol order. |
A language over
Operations on languages:
| Operation | Definition |
|---|---|
| Union | |
| Intersection | |
| Difference | |
| Complement | |
| Concatenation | |
| Iteration | |
| Kleene star |
Call union, concatenation, and iterative closure the regular operations.
A generative grammar is a quadruple
where:
| Component | Meaning |
|---|---|
| Nonterminal alphabet. | |
| Terminal alphabet, disjoint from | |
| Start symbol. | |
| Production rules |
A word
This is written
The Chomsky hierarchy classifies grammars by rule restrictions:
| Type | Name | Rule shape | Language class |
|---|---|---|---|
| 0 | Phrase-structure / unrestricted | No restriction except left side contains a nonterminal. | Recursively enumerable languages. |
| 1 | Context-sensitive | Context-sensitive languages. | |
| 2 | Context-free | Context-free languages. | |
| 3 | Regular | Regular languages. |
The hierarchy is strict:
Every regular language is context-free, every context-free language is context-sensitive in the usual nonempty-language sense with the
What to Emphasize in an Oral Answer
- Define alphabet, word/string, empty word
, , and concatenation with as identity. - Define a language as a subset of
and list both set operations and language operations, especially concatenation and Kleene star. - Identify union, concatenation, and Kleene star as the regular operations.
- Define a generative grammar
and explain derivation and generated language . - State the Chomsky hierarchy by rule restrictions: unrestricted, context-sensitive, context-free, and regular.
- Give the strict inclusion chain
. - Mention the usual context-sensitive
exception if the empty word is discussed.
Suggested answer
Formal language theory starts with alphabets and words. An alphabet is a finite nonempty set of symbols, and a word is a finite sequence of symbols over that alphabet. The empty word is denoted by
A language is simply a set of words. Languages can be combined by set operations such as union, intersection, difference, and complement, and also by language operations such as concatenation and Kleene star. These operations are important because regular languages are exactly the languages built from finite languages using union, concatenation, and iteration.
A generative grammar is a formal system for producing words. It consists of nonterminals, terminals, a start symbol, and production rules. A derivation starts from the start symbol and repeatedly replaces a left side of a rule by its right side. The language generated by the grammar is the set of all terminal words derivable from the start symbol.
The Chomsky hierarchy classifies grammars by how restricted their rules are. Type 0 grammars are unrestricted. Type 1 grammars are context-sensitive: a nonterminal may be rewritten only within a context, and the rule cannot shrink the word except for the special empty-word rule. Type 2 grammars are context-free: a single nonterminal is rewritten independently of context. Type 3 grammars are regular: rules are essentially right-linear. The corresponding language classes satisfy
12.2 Normal Forms of Grammars
A normal form is an equivalent grammar shape with simpler syntactic restrictions. Normal forms are useful because they preserve the generated language while making proofs and algorithms easier.
For type-3 grammars, every regular language can be generated by a grammar with only rules of the form:
where
For context-free grammars, Discuss three transformations.
First, empty right-hand sides can be eliminated except for the start symbol if the language contains
where
An
Second, a grammar is in Chomsky normal form if every production has one of these forms:
where
Chomsky normal form matters because derivations have a tree-like binary structure. A word of length
Third, a context-free grammar can be reduced by removing useless nonterminals.
| Concept | Meaning |
|---|---|
| Active nonterminal | Some terminal word can be derived from it. |
| Inactive nonterminal | No terminal word can be derived from it. |
| Reachable nonterminal | Appears in some sentential form derived from the start symbol. |
| Unreachable nonterminal | Cannot be reached from the start symbol. |
| Useless nonterminal | Inactive or unreachable. |
| Reduced grammar | Every nonterminal is active and reachable. |
It is decidable whether a nonterminal is active or reachable, and every context-free grammar can be transformed into an equivalent reduced grammar.
A derivation tree represents a context-free derivation as a tree. The root is labelled by
What to Emphasize in an Oral Answer
- Define a normal form as an equivalent grammar with restricted production shapes used for proofs and algorithms.
- For type-3 grammars, state the right-linear normal form
and . - For CFGs, explain elimination of
-rules, preserving only through a special start rule when needed. - Describe reduction of CFGs by removing inactive and unreachable nonterminals.
- State Chomsky normal form rules
and and that every -free CFG can be converted to it. - Explain why CNF matters: binary derivation trees support parsing and membership algorithms.
- Mention derivation trees and the role of leftmost derivations as a canonical derivation order for a tree.
Suggested answer
Normal forms are equivalent grammar shapes with stricter production rules. They are useful because they simplify algorithms and proofs without changing the language, except for controlled treatment of the empty word.
For regular grammars, a normal form uses rules such as
For context-free grammars, the first important cleanup is removing empty productions. If the language contains the empty word, a special new start rule may preserve it; otherwise the grammar can be made
The most important context-free normal form here is Chomsky normal form. Its rules are only
12.3 Regular Expressions
Regular expressions are a syntactic way to define regular languages. They are built recursively from alphabet symbols and regular operations.
Let
is a regular expression. - Every
is a regular expression. - If
is a regular expression, then is a regular expression. - If
and are regular expressions, then and are regular expressions.
The usual meanings are:
| Expression | Language denoted |
|---|---|
The list includes algebraic laws for regular expressions:
| Law | Form |
|---|---|
| Associativity of union | |
| Associativity of concatenation | |
| Commutativity of union | |
| Distributivity | |
| Identity | |
| Star unfolding | |
| Star with optional one-step | |
| Empty annihilator |
It also gives an inference rule similar to Arden's lemma:
The central theorem is:
Every regular expression denotes a regular language, and every regular language can be denoted by a regular expression.
This theorem connects expressions, regular grammars, and finite automata as equivalent descriptions of the same language class.
What to Emphasize in an Oral Answer
- Define regular expressions recursively from
, alphabet symbols, union, concatenation, and Kleene star. - Keep syntax and semantics separate: expressions denote languages.
- State the meanings of
, concatenation, star, , and . - Mention important algebraic laws: associativity, commutativity of union, distributivity, identities, empty-language annihilation, and star unfolding.
- Include Arden-style equation solving when relevant:
with gives . - State the central equivalence theorem: regular expressions, regular grammars, and finite automata define the same language class.
Suggested answer
Regular expressions are a compact notation for regular languages. They start from basic expressions for single symbols and the empty word, then combine them using union, concatenation, and Kleene star. The meaning is language-theoretic: union means alternative choice, concatenation means one word followed by another, and star means any finite number of repetitions, including zero repetitions.
The expression syntax is separate from semantics. For example,
Regular expressions satisfy algebraic laws such as associativity and commutativity of union, associativity of concatenation, distributivity of concatenation over union, and identities involving
The key theorem is that regular expressions describe exactly the regular languages. Every expression denotes a regular language because it is built using operations under which regular languages are closed. Conversely, every regular language accepted by a finite automaton can be expressed by a regular expression. Thus regular grammars, finite automata, and regular expressions are equivalent descriptions of the same class.
12.4 Finite Automata
Finite automata are recognizing devices for regular languages. A deterministic finite automaton is a quintuple
where:
| Component | Meaning |
|---|---|
| Finite nonempty set of states. | |
| Input alphabet. | |
| Transition function. | |
| Initial state. | |
| Accepting states. |
The automaton reads the input word from left to right. After the last symbol is read, it accepts if the current state is in
A nondeterministic finite automaton allows several possible next states:
An automaton may also permit a set
Automaton transitions can be viewed as rules:
when
For an NFA with initial-state set
Core equivalence theorems:
| Theorem | Meaning |
|---|---|
| NFA to regular grammar | For every NFA |
| Regular grammar to automaton | For every type-3 grammar |
| NFA to DFA | For every NFA there is an equivalent DFA. |
The NFA-to-DFA construction is the subset construction. DFA states are subsets of NFA states. On symbol
Accepting subsets are those intersecting
What to Emphasize in an Oral Answer
- Define a DFA by its finite states, input alphabet, transition function, initial state, and accepting states.
- Explain the run: read input left to right and accept exactly if the final state after the whole word is accepting.
- Contrast NFAs: a state and symbol may have several possible next states, and acceptance means some run accepts.
- Mention multiple initial states or empty-word acceptance conditions when they appear in the model.
- State subset construction: DFA states are subsets of NFA states, accepting subsets intersect the NFA accepting set.
- Emphasize that nondeterminism does not increase finite-automaton expressive power, though it may reduce description size.
- State equivalence with regular grammars and regular expressions.
Suggested answer
A finite automaton is a finite-state recognizer for words. It has a finite set of states, an input alphabet, a transition function, an initial state, and a set of accepting states. It reads the input from left to right, updating its state after each symbol. When the input is finished, the word is accepted exactly if the automaton is in an accepting state.
In a deterministic finite automaton, each pair of current state and input symbol determines exactly one next state. In a nondeterministic finite automaton, a pair may determine several next states, or none. A nondeterministic automaton accepts a word if at least one possible run reaches an accepting state.
The important result is that deterministic and nondeterministic finite automata recognize the same languages. The subset construction turns an NFA into a DFA by making each DFA state a set of possible NFA states. This can increase the number of states, but it does not change the accepted language.
Finite automata are equivalent to regular grammars and regular expressions. From an automaton one can construct a regular grammar whose nonterminals behave like states. From a regular grammar one can build an automaton whose transitions simulate productions. Therefore finite automata are exactly the recognizing model for regular languages.
12.5 Pushdown Automata
Pushdown automata recognize context-free languages by adding a stack to finite control. A pushdown automaton can be defined as
where:
| Component | Meaning |
|---|---|
| Finite stack alphabet. | |
| Finite set of states. | |
| Input alphabet. | |
| Transition function. | |
| Initial stack symbol. | |
| Initial state. | |
| Accepting states. |
A configuration records the stack content, current state, and unread input. One compact notation combines stack and state into words such as
If the top stack symbol is
means: replace top stack symbol
Acceptance by final state:
Acceptance by empty stack:
State two equivalence theorems:
| Theorem | Meaning |
|---|---|
| CFG to PDA | For every context-free grammar |
| PDA to CFG | For every PDA |
Thus pushdown automata and context-free grammars are equivalent in expressive power.
Determinism for pushdown automata is stricter than for finite automata. For each pair of top stack symbol and state, either exactly one input-consuming move is available for each input symbol and no
What to Emphasize in an Oral Answer
- Define a PDA as finite control plus a stack, with stack alphabet, input alphabet, transition relation, initial stack symbol/state, and final states.
- Explain a transition: inspect state, top stack symbol, and input symbol or
; replace the top stack symbol, change state, and optionally consume input. - Use the stack's LIFO memory to explain matching and nesting, the typical context-free behavior.
- Distinguish acceptance by final state and acceptance by empty stack; for nondeterministic PDAs they are equivalent in expressive power.
- State both equivalence theorems: CFGs can be simulated by PDAs and PDAs can be converted to CFGs.
- Highlight the contrast with finite automata: deterministic and nondeterministic PDAs are not equivalent in power.
Suggested answer
A pushdown automaton is a finite automaton equipped with a stack. The finite control stores the current state, while the stack stores unbounded last-in-first-out information. A transition looks at the current state, the top stack symbol, and either the next input symbol or
This stack is exactly what makes pushdown automata suitable for context-free languages. Finite automata cannot count arbitrarily nested or matched structures, but a stack can remember pending symbols. For example, a PDA can push symbols while reading one part of a word and pop them while reading a matching later part.
There are two common acceptance modes. Acceptance by final state means that after reading the input the automaton reaches an accepting state. Acceptance by empty stack means that after reading the input the stack has been reduced to empty, regardless of final state. These acceptance conventions are equivalent in expressive power for nondeterministic pushdown automata, with suitable constructions.
The key theorem is that pushdown automata recognize exactly the context-free languages. Every context-free grammar can be simulated by a PDA, and every PDA can be converted into a context-free grammar. Determinism is more delicate here than for finite automata: nondeterministic finite automata can always be determinized, but nondeterministic pushdown automata are more powerful than deterministic ones.
12.6 Closure Properties of Language Classes
Closure properties state whether applying an operation to languages in a class always produces another language in the same class.
every Chomsky class
Regular languages are closed under:
| Operation | Reason or construction |
|---|---|
| Union | Product construction or NFA branching. |
| Concatenation | NFA connects final states of the first automaton to the start of the second. |
| Kleene star | NFA loops from accepting states back to the start and allows |
| Intersection | Product automaton tracks both input automata. |
| Complement | Complete a DFA and swap accepting/nonaccepting states. |
| Difference | |
| Reversal | Reverse automaton edges and swap start/final roles using an NFA. |
Context-free languages are closed under:
| Operation | Status |
|---|---|
| Union | Closed. Add a new start symbol with alternatives to the two grammars. |
| Concatenation | Closed. Add a start rule combining the two start symbols. |
| Kleene star | Closed. Add recursive start rules for repeated copies. |
| Reversal | Closed. Reverse right-hand sides of grammar rules. |
| Intersection with regular language | Closed. Combine a PDA with a finite automaton. |
Context-free languages are not closed under:
| Operation | Caution |
|---|---|
| General intersection | Two CFLs can intersect to a non-CFL. |
| Complement | If CFLs were closed under complement, closure under union would imply closure under intersection by De Morgan, which is false. |
| Difference | Difference with an arbitrary CFL would imply complement. |
The broader Chomsky hierarchy has additional closure facts, but for the subject the most important practical contrast is: regular languages have robust Boolean closure; context-free languages are closed under the grammar-building operations but not under arbitrary Boolean operations.
What to Emphasize in an Oral Answer
- Define closure under an operation and apply it to language classes.
- State that the Chomsky classes are closed under regular operations: union, concatenation, and Kleene star.
- For regular languages, list strong closures: union, concatenation, star, intersection, complement, difference, and reversal.
- Tie regular closures to automata constructions such as product automata, DFA complementation, and reversing edges with an NFA.
- For context-free languages, list positive closures: union, concatenation, star, reversal, and intersection with a regular language.
- State the negative CFL closures: not closed under arbitrary intersection, complement, or difference.
- Explain the De Morgan reason why complement closure plus union closure would imply intersection closure.
Suggested answer
A language class is closed under an operation if applying that operation to languages in the class always gives a language still in the class. The Chomsky classes are closed under the regular operations: union, concatenation, and Kleene star. Regular languages have even stronger closure properties. They are closed under union, concatenation, Kleene star, intersection, complement, difference, and reversal. The automata constructions explain this: union and intersection use product or nondeterministic constructions, complement swaps accepting and nonaccepting states in a complete DFA, and difference is intersection with a complement.
Context-free languages have weaker closure properties. They are closed under union, concatenation, Kleene star, and reversal because grammars can be combined or transformed to produce these languages. They are also closed under intersection with a regular language, because a pushdown automaton can be run together with a finite automaton.
However, context-free languages are not closed under arbitrary intersection, complement, or difference. This is a central contrast with regular languages. The reason complement closure would be too strong is that, together with union closure, it would imply intersection closure by De Morgan's laws, but context-free languages are known not to be closed under intersection.
So for oral exam purposes, the safe summary is: regular languages are closed under both regular operations and Boolean operations; context-free languages are closed under the constructive operations used by grammars, but not under general Boolean operations.
12.7 Algorithmic Problems for Regular and Context-Free Languages
An algorithmic problem asks whether there is an effective procedure deciding a property of a grammar, automaton, or language.
For regular languages, many central problems are decidable because finite automata have finitely many states and can be analyzed as finite graphs.
| Problem | Regular-language method |
|---|---|
| Membership | Run the DFA or simulate the NFA on the word. |
| Emptiness | Check whether an accepting state is reachable from an initial state. |
| Finiteness | Check whether a cycle lies on some path from the initial state to an accepting state. |
| Equivalence | Minimize DFAs or test emptiness of the symmetric difference. |
| Inclusion | Test emptiness of |
For context-free languages, the main decidability results are:
| Problem | Context-free-language method or theorem |
|---|---|
| Membership | Decidable; Chomsky normal form supports parsing algorithms such as CYK. |
| Emptiness | Decidable; remove inactive/unreachable nonterminals or test whether the start symbol can derive a terminal word. |
| Finiteness/infiniteness | Decidable; use grammar graph/cycle analysis after reduction. |
Also include the Bar-Hillel lemma, a pumping lemma for context-free languages. For every context-free language
with
and
for every
This lemma is mainly a proof tool for showing that some languages are not context-free. The exact notation differs across textbooks; the core idea is that in a long enough derivation tree, a nonterminal repeats along a path, allowing two parts of the word to be pumped together.
Important cautions for context-free languages:
| Problem | Status |
|---|---|
| Equivalence of arbitrary CFGs | Undecidable. |
| Inclusion of arbitrary CFGs | Undecidable. |
| Ambiguity of arbitrary CFGs | Undecidable. |
| Universality of CFGs | Undecidable. |
These negative results explain why normal forms and decidable subproblems are important: context-free grammars are useful and analyzable in some ways, but not all natural questions about them have algorithms.
What to Emphasize in an Oral Answer
- Define algorithmic problems as decidability questions about grammars, automata, and languages.
- For regular languages, mention why many problems are decidable: finite automata are finite graphs.
- State regular-language methods for membership, emptiness, finiteness, equivalence, and inclusion.
- For context-free languages, list the main decidable problems: membership, emptiness, and finiteness/infiniteness.
- Mention Chomsky normal form and parsing algorithms such as CYK for CFG membership.
- State the Bar-Hillel pumping lemma's purpose: long CFL words have pumpable paired parts, used mainly to prove languages are not CFLs.
- Name the major undecidable CFG problems: equivalence, inclusion, ambiguity, and universality.
Suggested answer
Algorithmic problems ask what properties of languages, grammars, and automata can be decided by an algorithm. For regular languages, the main questions are decidable because finite automata are finite graphs. Membership is decided by running the automaton. Emptiness is decided by reachability of an accepting state. Finiteness is decided by checking whether there is a cycle on a path from the start to an accepting state. Equivalence and inclusion are also decidable, for example by using complement and intersection to reduce them to emptiness.
For context-free languages, several important problems remain decidable. Membership is decidable, and Chomsky normal form gives a basis for parsing algorithms. Emptiness is decidable by checking whether the start symbol can derive some terminal word, which is related to removing inactive and unreachable nonterminals. Infiniteness is also decidable by analyzing whether a reduced grammar can generate arbitrarily long words.
The Bar-Hillel lemma is a pumping lemma for context-free languages. It says that every sufficiently long word in a context-free language has two parts that can be repeated together while staying in the language. This is usually used negatively: to prove a language is not context-free, assume it is context-free, take a long enough word, and show that every possible pumping decomposition eventually leaves the language.
The important caution is that context-free languages are not algorithmically tame in every respect. Equivalence, inclusion, universality, and ambiguity of arbitrary context-free grammars are undecidable. Thus regular languages have a very complete finite-state decision theory, while context-free languages have useful decidable problems but also important undecidable boundaries.
