Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
| theocs:lecture5-6 [2024/10/17 13:28] – [Pumping lemma] tami | theocs:lecture5-6 [2024/10/17 13:33] (current) – [Pumping lemma] tami | ||
|---|---|---|---|
| Line 49: | Line 49: | ||
| **Theorem (Pumping Lemma)** | **Theorem (Pumping Lemma)** | ||
| - | Let $L$ be an infinite regular language accepted by a DFA with $m$, states. Then any string $w$ in $L$ with at least $m$ symbols can be decomposed as $w = xyx$ with $|xy \leq m$, and $|y| \geq 1$ such that | + | Let $L$ be an infinite regular language accepted by a DFA with $m$, states. Then any string $w$ in $L$ with at least $m$ symbols can be decomposed as $w = xyx$ with $|xy| \leq m$, and $|y| \geq 1$ such that |
| $$w_i = \underbrace{xy...yz}_i$$ | $$w_i = \underbrace{xy...yz}_i$$ | ||
| Line 59: | Line 59: | ||
| We can prove **by contradiction** that $L = \{a^n b^n, n \geq 0 \}$ is not regular using the pumping lemma. | We can prove **by contradiction** that $L = \{a^n b^n, n \geq 0 \}$ is not regular using the pumping lemma. | ||
| + | |||
| + | |||