Preamble

Finite automata is used in text processing (lexical analysis) Pushdown automata is used in parsing The Turing Machine is a more general kind of automaton which is universal

Formal Languages

Alphabet

An alphabet is a finite set $S$ of symbols. Examples of alphabets include: $\{a,b,c,...,z\}$, $\{0,1\}$ and $\{\#,\text{!},\text{=}\}$.

Link to original

Word (finite automata)

A word or string (over an alphabet $S$) is a finite sequence of symbols from $S$ written without commas. For example, $tortoise,abc$ or $11101110101011,1110$.

Link to original

Language

A language (over an alphabet $S$) is a set of words over $S$.

For example, given $S=\{a,b,c,...,z\}$.

• $L_1=\text{ all English words}$
• $L_2=\text{ all Latin words}$
• $L_3=\{ghgkrf,oputj,erwwq\}$

Given $S=\{0,1\}$:

• $L_4=\{001,101010,111,1001\}$
• $L_5=\{0^n{1}^m|n\text{ is even},m\text{ is odd}\}$

Link to original

Chomsky hierarchy

Depending on the form of the language, identifying valid words can vary in difficulty.

Chomsky hierarchy

The Chomsky hierarchy categorises languages into collections according to their difficulty.

Type	Abstract Machine
Type-0	Turing Machine
Type-1	Linear-bounded Turing Machine
Type-2	Pushdown Automata
Type-3	Finite Automata

Each level has varying memory capabilities.

Link to original

Finite Automata

Finite automata (or finite-state machines) with alphabet $\mathcal{X}$ is defined by a finite number of states and a set of transitions between states (one transition for each symbol in $\mathcal{X}$).

There is a distinguished state, called initial state, indicated by an arrow where the automaton starts, and one or more final / accepting states indicated by double circle.

Finite automata

A finite automata is a tuple $(\mathcal{X},\mathcal{Q},q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $q_i\in \mathcal{Q}$ is the initial state
• $F\subseteq \mathcal{Q}$ is the set of accepting states
• $\delta :\mathcal{Q}\times \mathcal{X}\to \mathcal{Q}$ is the transition function

Link to original

The language associated with a finite automaton $A$ is the set of words it accepts, denoted $L(A)$.

Example: A vending machine

graph LR;
	start(( ));
	0((0));
	5((5));
	10((10));
	15((15));
	20(((20)));
	start-->0;
	
	0-- 5 -->5;
	5-- 5 -->10;
	10-- 5 -->15;
	15-- 5 -->20;

	0-- 10 -->10;
	5-- 10 -->15;
	10-- 10 -->20;
	
	0-- 20 -->20;

$\mathcal{X}=\{5p,10p,20p\}$ $\mathcal{L}=$ any sequence of coins adding exactly to 20p

• $[5,10,5]$: valid word, terminates in accepting state
• $[10,5]$: invalid word, terminates in non-accepting state
• $[10,5,10]$: invalid word, no valid transition

Exercises

Deterministic and Non-Deterministic Finite Automata

Non-deterministic finite automata

A non-deterministic finite automata is a tuple $(\mathcal{X},\mathcal{Q},q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $q_i\in \mathcal{Q}$ is the initial state
• $F\subseteq \mathcal{Q}$ is the set of accepting states
• $\delta :\mathcal{Q}\times (\mathcal{X}\cup ϵ)\to \mathcal{P}(\mathcal{Q})$ is the transition function
  • $\mathcal{P}(\mathcal{Q})$ is the power set of $\mathcal{Q}$
  • $ϵ$ is an empty transition label that can be taken at any point when reading a word

A word is accepted if there is any trace from the initial state to an accepting state.

Link to original

Example: NDFA

graph LR;
	start(( ));
	p((p));
	q(((q)));
	start-->p;
	
	p-- 0,1 -->p;
	p-- 1 -->q;

Is $1011$ a valid word?

• $p{\to }^{1}q$: non-accepting trace
• $p{\to }^{1}p{\to }^{0}p{\to }^{1}q$: non-accepting trace
• $p{\to }^{1}p{\to }^{0}p{\to }^{1}p{\to }^{1}q$: accepting trace
• $p{\to }^{1}p{\to }^{0}p{\to }^{1}p{\to }^{1}p$: non-accepting trace

Non-deterministic and deterministic finite automata are computationally equivalent. A language can be recognised by an NFA iff the language can be recognised by a DFA.

Power of finite automata

• They have no ‘memory’, no knowledge of previous state.
• This limits languages we can associate (these are regular languages)
• Regular languages are closed under basic set operations (union, intersect)
• A language that is not pumpable is not regular.

The Pumping Lemma (Theorem)

The Pumping Lemma says if $L\subseteq {\Sigma }^{\ast }$ is a regular language then there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$ for $x,y,z\in {\Sigma }^{\ast }$ such that:

• If $|xy|\le p$ and $|y|>0$,
• then $x{y}^{n}z\in L$ for all $n\ge 0$.

Link to original

Pushdown automata

Pushdown automata (PDA) are finite automata but with a stack. The stacks in the PDA store symbols.

Stack

Stacks are specialised forms of memory where:

• only the top of the stack can be read (pop) and in the process it is removed from the stack
• new elements must be added to the top of the stack (push)

Link to original

Pushdown automata

A pushdown automata (PDA) is a tuple $(\mathcal{X},\mathcal{Q},\Gamma ,q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $\Gamma$ is the set of symbols that can be stored on stack
• $q_i\in \mathcal{Q}$ is the initial state
• $F\subseteq \mathcal{Q}$ is the set of accepting states
• $\delta :\mathcal{Q}\times (\mathcal{X}\times ϵ)\times (\Gamma \cup ϵ)\to \mathcal{P}((\mathcal{Q}\times (\Gamma \cup ϵ)))$ is the transition function

The transition function $\delta$ maps $(state,letter,symbol)$ to a set of pairs of the form $(state,symbol)$.

• Symbol in domain is to be popped.
• Symbol in co-domain is to be pushed.
• If symbol is $ϵ$ (empty), nothing is to be popped / pushed.

Transitions may also be labelled $ϵ$. A word is accepted if there is any trace from initial state to accepting state that leaves the stack empty.

Link to original

Example: PDA

graph LR;
	start(( ));
	p((p));
	q((q));
	r(((r)));
	start-->p;
	
	p-- (0, ε); A -->p;
	p-- (ε, ε); ε --> q;
	q-- (1, A); ε -->q;
	q-- (ε, ε); ε -->r;

Transition notation is $(a,b);c$ where:

• $a$ is the next character of word
• $b$ is symbol to be popped from stack
• $c$ is symbol to be pushed to stack

Is $0011$ a valid word?

Exercises

For the PDA example above:

More exercises:

Power of PDA

• They have limited memory
• Limits languages the PDA can be associated with to Type-2 languages
• These are called context-free languages