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:17] – [Lecture A/6: What is beyond regular languages?] tami | theocs:lecture5-6 [2024/10/17 13:33] (current) – [Pumping lemma] tami | ||
|---|---|---|---|
| Line 37: | Line 37: | ||
| Given a language, is there a way to determine whether it is regular? | Given a language, is there a way to determine whether it is regular? | ||
| + | |||
| + | One possibility for proving the language is not regular is using the **pumping lemma**, which applies for infinite languages (All finite languages are regular!) | ||
| <WRAP center round info 60%> | <WRAP center round info 60%> | ||
| - | **Theorem (The pigeon hole principle** | + | **Theorem (The pigeon hole principle)** |
| If we put $n$ into $m$ pigeonholes ($n>m$), then at least one pigeon hole must have more than one pigeon! | If we put $n$ into $m$ pigeonholes ($n>m$), then at least one pigeon hole must have more than one pigeon! | ||
| </ | </ | ||
| + | |||
| + | <WRAP center round info 60%> | ||
| + | **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 | ||
| + | |||
| + | $$w_i = \underbrace{xy...yz}_i$$ | ||
| + | |||
| + | 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. | ||