Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
| theocs:lecture5-6 [2024/10/17 13:32] – [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$$ | ||