Automata and regular languages

Vocabulário

English	Significado
deterministic finite automaton	deterministic finite automaton
pumping lemma	pumping lemma

English

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}

Prática

The course DFA on input aba ends in state —

Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje

English

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}

Prática

The pumping lemma shows a^n b^n is not regular because —

Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje

English

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}

Prática

The trace of aabab in the ends-in-ab DFA is —

Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje