Automata and regular languages
Introduced
Vocabulary
| English | Meaning |
|---|---|
| deterministic finite automaton | deterministic finite automaton |
| pumping lemma | pumping lemma |
The table machine
- A deterministic finite automaton is states plus a transition table: read a symbol, move, accept or reject at the end of input. The course DFA accepts strings over $\{a, b\}$ ending in $ab$.
{exercise:uni-cs1101-dfa}
Practice
The course DFA on input aba ends in state —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
q0-a-q1, q1-b-q2, q2-a-q1: ends q1, rejected (q2 accepts, not q1).
The pumping ceiling
- The pumping lemma: any long accepted string splits $xyz$ with $|xy| \le p$, $|y| \ge 1$, and every $xy^iz$ accepted — so $L = \{a^n b^n\}$ is NOT regular: pump $y$ (all $a$'s) and the count breaks.
- Regular languages cannot count unboundedly — memoryless is the ceiling.
{exercise:uni-cs1101-pumping}
Practice
The pumping lemma shows a^n b^n is not regular because —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
y lies in the a-block; pumping changes the count of a without b.
Traces, exactly
aababwalks q0→q1 (a), q1→q1 (a), q1→q2 (b), q2→q1 (a), q1→q2 (b) — accept.abawalks q0, q1, q2, q1 — reject (ends mid-pattern).- Regex
ab|baas an NFA guesses the branch; the subset-construction DFA tracks both possibilities at once — determinisation can square the state count.
{exercise:uni-cs1101-trace}
Practice
The trace of aabab in the ends-in-ab DFA is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
a:q1, a:q1, b:q2, a:q1, b:q2 - accept.