Differences

This shows you the differences between two versions of the page.

--- theocs:lecture5-6 [2024/10/17 13:12] – [Lecture A/6: What is beyond regular languages?] tami
+++ theocs:lecture5-6 [2024/10/17 13:33] (current) – [Pumping lemma] tami
@@ Line 21: / Line 21: @@
 $$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$ Is not finate! it is impossible to create an automaton that can satisfy it!
+$\{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!
 </WRAP>
-Every final state has a additional production,
+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>
+<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...$
+</WRAP>
+**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.
-$$A \to \Lambda$$