Unit 1: Automata and regular languages
Theory of Computation notes · PTU syllabus (PGCA1927)
On this page
- Unit summary
- Formal languages
- The diagonal argument
- Deterministic finite automata
- Non-deterministic finite automata and equivalence
- Mealy and Moore machines
- Minimisation of finite automata
- Regular expressions, regular grammars and regular languages
- The pumping lemma and non-regular languages
- Lexical analysis
- Key terms
- Quick revision
- Important questions
Unit summary
The theory of computation asks what machines can compute and how efficiently. This unit covers formal languages, the diagonal argument, deterministic and non-deterministic finite automata and their equivalence, Mealy and Moore machines, minimisation of finite automata, regular languages, grammars and expressions, the pumping lemma, non-regular languages and lexical analysis.
After this unit you can
- Define alphabets, strings and languages and explain the diagonal argument
- Design DFAs and NFAs and convert NFAs to DFAs
- Build Mealy and Moore machines and minimise DFAs
- Use regular expressions and grammars and prove non-regularity with the pumping lemma
PTU syllabus topics
- Formal language
- diagonal argument
- deterministic and non-deterministic finite automata and their equivalence
- Mealy and Moore models
- finite automata minimization
- regular languages/grammars/expressions
- pumping lemma
- non-regular languages
- lexical analysis
Transitions per input
Exactly one
Zero, one or many
ε-moves
Not allowed
Allowed (ε-NFA)
Power
Same: regular languages
Same: regular languages
Size
Can be exponentially larger
Often smaller
Topic 1
Formal languages
- Alphabet (Σ)
- Finite set of symbols — {0, 1}
- String
- Finite sequence of symbols; ε is the empty string
- Length
- Number of symbols, written as the length of w
- Σ∗
- All strings over Σ including ε; Σ⁺ excludes ε
- Language
- Any subset of Σ∗
- Operations
- Union, concatenation, Kleene star, reversal, complement
Example
Over Σ = {a, b}: L1 = {a, ab, abb}; L2 = strings with an even number of a's (infinite).
Topic 2
The diagonal argument
- Cantor's diagonalisation shows some sets are uncountable: list all infinite binary sequences; build a new sequence whose ith bit differs from the ith bit of the ith sequence — it is not in the list.
- Consequence for computing: the set of programs (finite strings) is countable, but the set of languages over Σ is uncountable — so most languages have no program that decides them. The same idea proves the halting problem undecidable.
Topic 3
Deterministic finite automata
- A DFA is a 5-tuple (Q, Σ, δ, q0, F): states, alphabet, transition function δ: Q × Σ → Q, start state and accepting states. Exactly one move per symbol.
q0 (start)
q1
q0
q1 (seen 0)
q1
q2
q2 (accept: seen 01)
q1
q0
Example
Input 1101: q0 →1 q0 →1 q0 →0 q1 →1 q2 — accepted. Input 0110 ends in q1 — rejected.
Topic 4
Non-deterministic finite automata and equivalence
- An NFA allows zero, one or many moves per symbol and ε-moves: δ: Q × (Σ ∪ {ε}) → subsets of Q. It accepts if some path ends in an accepting state.
- 1Start state of the DFA = ε-closure of the NFA start state
- 2For each DFA state (a set of NFA states) and symbol, compute the ε-closure of all reachable states
- 3Each new set becomes a DFA state
- 4A DFA state is accepting if it contains an NFA accepting state
- 5Repeat until no new sets appear
- Equivalence: every NFA has an equivalent DFA (possibly with up to 2ⁿ states), so NFAs and DFAs recognise exactly the regular languages.
Topic 5
Mealy and Moore machines
Output depends on
Current state only
Current state and input
Output timing
Associated with states
Associated with transitions
Output length
One more than input length (includes start state)
Same as input length
Size
May need more states
Often fewer states
- Each can be converted to the other. Example: a Mealy machine outputting 1 whenever the last two inputs are equal (sequence detector), or a Moore machine giving the remainder of a binary number mod 3.
Topic 6
Minimisation of finite automata
- 1Remove unreachable states
- 2Partition states into accepting and non-accepting groups
- 3Split a group if two states go to different groups on some symbol
- 4Repeat until no group splits
- 5Each final group becomes one state of the minimal DFA
- The minimal DFA for a regular language is unique up to renaming of states (Myhill–Nerode theorem).
Topic 7
Regular expressions, regular grammars and regular languages
- Basic
- ∅, ε and each symbol a
- Union
- r + s (or r, s alternatives)
- Concatenation
- rs
- Kleene star
- r∗ — zero or more repetitions
- Examples
- (0 + 1)∗01 — strings ending in 01; a∗b∗ — a's followed by b's
- Kleene's theorem: a language is regular if and only if some regular expression describes it, if and only if some finite automaton accepts it. Thompson's construction converts a regular expression to an ε-NFA.
- Regular grammar: productions of the form A → aB or A → a (right-linear); regular grammars generate exactly the regular languages.
- Union, concatenation, star
- Closed
- Intersection, complement, difference
- Closed
- Reversal, homomorphism
- Closed
Topic 8
The pumping lemma and non-regular languages
- Pumping lemma: if L is regular, there is a constant p such that every string w in L with length at least p can be split as w = xyz with y non-empty and the length of xy at most p, so that xyⁱz is in L for all i ≥ 0.
Example
L = {aⁿbⁿ : n ≥ 0} is not regular. Take w = aᵖbᵖ. Since xy has at most p symbols, y consists only of a's. Pumping (i = 2) gives more a's than b's, which is not in L — contradiction.
- Other non-regular languages: palindromes, balanced parentheses, {0ⁿ² : n ≥ 0}. Finite automata cannot count without bound.
Topic 9
Lexical analysis
- The lexical analyser of a compiler reads source characters and groups them into tokens (identifiers, keywords, numbers, operators) using regular expressions; tools such as Lex/Flex convert the regular expressions into a DFA.
Example
Identifier: letter (letter + digit)∗; integer: digit digit∗. The input "sum1 = 42" produces tokens ID(sum1), ASSIGN, NUM(42).
Key terms
- Alphabet
- Finite set of symbols
- DFA
- Finite automaton with exactly one transition per symbol
- NFA
- Finite automaton allowing several or ε transitions
- Regular expression
- Algebraic notation describing a regular language
- Pumping lemma
- Property of regular languages used to prove non-regularity
Quick revision
- Σ, strings, Σ∗, languages and operations; diagonalisation.
- DFA 5-tuple; NFA, ε-NFA; subset construction.
- Mealy (output on transitions) vs Moore (output on states).
- Minimisation by partitioning; Myhill–Nerode.
- Regular expressions, Kleene's theorem, regular grammars, closure, pumping lemma, lexical analysis.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a DFA formally.
- Q2.Distinguish a DFA and an NFA.
- Q3.Distinguish Mealy and Moore machines.
- Q4.Write a regular expression for strings over {a, b} containing aa.
- Q5.State the pumping lemma for regular languages.
- Q6.What does a lexical analyser do?
Long-answer questions
- Q1.Design a DFA for a given language and trace inputs.
- Q2.Convert an NFA to a DFA using subset construction.
- Q3.Explain minimisation of a DFA with an example.
- Q4.Prove that {aⁿbⁿ} is not regular using the pumping lemma.
Stuck on this unit?
Message SBS on WhatsApp for help with Theory of Computation, or to ask about studying M.Sc IT at Synetic.