Automata and regular languages
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| 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}
Luyện tập
The course DFA on input aba ends in state —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
q0-a-q1, q1-b-q2, q2-a-q1: ends q1, rejected (q2 accepts, not q1).
English
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}
Luyện tập
The pumping lemma shows a^n b^n is not regular because —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
y lies in the a-block; pumping changes the count of a without b.
English
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}
Luyện tập
The trace of aabab in the ends-in-ab DFA is —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
a:q1, a:q1, b:q2, a:q1, b:q2 - accept.