Table of Contents
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.
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
$\{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!)
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!
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.