theocs:lecture5-6

Differences

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

Link to this comparison view

Next revision		 Previous revision
theocs:lecture5-6 [2024/10/17 12:15] – created tamitheocs:lecture5-6 [2024/10/17 13:33] (current) – [Pumping lemma] tami
Line 9: Line 9:
  
 {{:theocs:screenshot_2024-10-17_at_13-14-37_lecture_a_5_finite_automata_and_regular_languages_-_lecture05_a_slides.pdf.png?400|}} {{:theocs:screenshot_2024-10-17_at_13-14-37_lecture_a_5_finite_automata_and_regular_languages_-_lecture05_a_slides.pdf.png?400|}}
 +
 +====== Lecture A/6: What is beyond regular languages? ======
 +
 +A **Regular grammar** is on e where each production takes on fo the following restricted forms:
 +  * $N \to \Lambda$
 +  * $N \to w$
 +  * $N \to A$
 +  * $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!
 +</WRAP>
 +
 +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.
 +
  
  • theocs/lecture5-6.1729167336.txt.gz
  • Last modified: 2024/10/17 12:15
  • by tami