Automata and regular languages

Vocabulary

English	Meaning
deterministic finite automaton	A finite-state machine with one transition for each state and input symbol.
pumping lemma	A necessary property of regular languages used to prove that some languages are not regular.

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

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

aabab walks q0→q1 (a), q1→q1 (a), q1→q2 (b), q2→q1 (a), q1→q2 (b) — accept. aba walks q0, q1, q2, q1 — reject (ends mid-pattern).
Regex ab|ba as 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