theocs:lecture5-6 [TamiWiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Lecture A/5: Finite Automata and Regular Languages ======

  * Generally, it's easier to find a NFA to accept a given language, but easier to program a DFA.
  * It is asserted that both FDAs and NFAs recognise the regular languages, which themselves are represented by regular expressions.

{{:theocs:screenshot_2024-10-17_at_13-13-33_lecture_a_5_finite_automata_and_regular_languages_-_lecture05_a_slides.pdf.png?400|}}

{{:theocs:screenshot_2024-10-17_at_13-14-28_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.