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$$
$a^n b^n$ Is not finite! it is impossible to create an automaton that can satisfy it!