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:25] – [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 55: | Line 55: | ||
| is also in $L$ for all $i = 0,1,2...$ | is also in $L$ for all $i = 0,1,2...$ | ||
| </ | </ | ||
| + | |||
| + | **We can use the pumping lemma to prove a language is not regular**, but not that it is regular! | ||
| + | |||
| + | We can prove **by contradiction** that $L = \{a^n b^n, n \geq 0 \}$ is not regular using the pumping lemma. | ||
| + | |||