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:05] – tami | theocs:lecture5-6 [2024/10/17 13:33] (current) – [Pumping lemma] tami | ||
|---|---|---|---|
| Line 13: | Line 13: | ||
| A **Regular grammar** is on e where each production takes on fo the following restricted forms: | A **Regular grammar** is on e where each production takes on fo the following restricted forms: | ||
| - | * $N \arrowright | + | * $N \to \Lambda$ |
| - | * $N \arrowright | + | * $N \to w$ |
| - | * $N \arrowright | + | * $N \to A$ |
| - | * $N \arrowright | + | * $N \to wA$ |
| + | |||
| + | Every transition is associated witha grammar production, e.g. if the state $1$ corresponds to the nonterminal $A$, them | ||
| + | |||
| + | $$T(S,a) = 1 \Leftrightarrow S \to aA$$ | ||
| + | |||
| + | Every final state has a additional production, | ||
| + | |||
| + | $$A \to \Lambda$$ | ||
| + | |||
| + | ===== Pumping lemma ===== | ||
| + | |||
| + | |||
| + | <WRAP center round important 60%> | ||
| + | $\{a^n b^n | n > 0\}$ Is not finite! it is impossible to create an automaton that can satisfy it! | ||
| + | |||
| + | * The automation would have to remember the number of $a$'s it has seen, which might be arbitrarily large | ||
| + | * **This is impossible for a machine with a finite number of possible states.** Any algorithm will break down when $n$ exceeds the number of states of the machine! | ||
| + | </ | ||
| + | |||
| + | 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%> | ||
| + | **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! | ||
| + | </ | ||
| + | |||
| + | <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. | ||