This is an old revision of the document!
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?
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!