1. Applications of finite automata

Finite automata

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

Examples include:

• spell checkers
• search engine pattern matching
• compiler design
• specifying network protocols
• chip design
• speech recognition
• transforming text using markup languages like XML
• software optimisation

Link to original

2. Alphabets, words, languages

Words

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

Empty word

The empty word, denoted by $ϵ$, is a word over any alphabet. We assume that $ϵ$ is not a symbol of any of our alphabets.

Link to original

Length (word)

The length of a word $w$ is $|w|=\text{ the number of symbols in }w$. For example, $|azwza|=5$ or $|ϵ|=0$.

Link to original

Concatenation

The concatenation of words $x$ and $y$ is the word $x$ followed by the word $y$, written $xy$. We can use the syntax $\text{foo}@\text{bar}=\text{foobar}$.

Formally, $A@B\stackrel{def}{=}\{s_1@s_2|s_1\in A\wedge s_2\in B\}$.

Link to original

Repetition

The repetition of words can be denoted by the power, $w^n=\stackrel{n}{\overbrace{ww...w}}$. For example, $(ab{)}^0=ϵ$, $(01{)}^3=010101$ or $a^4=aaaa$.

Link to original

For every word $x$, $xϵ=ϵx=x$.

Prefix

If $w=xyz$, then $xy$ is a prefix of $w$.

Link to original

Suffix

If $w=xyz$, then $yz$ is a suffix of $w$.

Link to original

Languages

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

Link to original

3. Finite automata basics

Finite automata basics

A theoretical model for programs using a constant amount of memory regardless of the input form.

Finite control device

Finite control device: in any moment, it can be in one of its states, it is hard-wired in how it changes from one state to another. There are also some special states, such as one initial state and possible more favourable states.

• Has a reading head.
• It reads from an input tape: divided into cells, having a leftmost cell, each cell contains one character of the input alphabet and is fed into the machine.

Link to original

Starting finite automation

• The finite control device is put in its unique initial state.

• The tape contains a finite word of the input alphabet, the input, as its left end. The remainder of the tape contains only blank cells.

• The reading head is positioned on the leftmost cell of the input tape, containing the first character of the input word.

  $$\begin{array}{l}\downarrow \text{reading head}\\ \begin{array}{ccccccccc}a& b& c& b& b& a& \text{textvisiblespace}& \text{textvisiblespace}& ...\end{array}\end{array}$$

How it works

At regular time intervals, the automaton:

• reads one character from the input tape
• moves the reading head one cell to the right, and
• chooses the next state of its control device

The control device is hard-wired such that the next state depends on:

1. the previous state
2. the character read from the tape

As the input is finite, at some moment the reading head reaches the end of the input word (the first blank cell). If at this moment the control device is in a favourable state, then the input word is accepted by the automaton. Otherwise, the input word is not accepted, rejected.

Used for

• Each finite automaton is a kind of ‘recognition’ or ‘decision’ device over all possible words of its input alphabet.

• Each automaton can be ‘tried’ on infinitely many input words, and gives a Y/N answer each time.

  $$\begin{array}{rl}abbbbaba& \to \boxed{A}\to \text{YES}\\ aba& \to \boxed{A}\to \text{NO}\\ ϵ& \to \boxed{A}\to \text{YES}\\ \text{...}& \to \boxed{A}\to \text{...}\end{array}$$

Link to original

4. State transition diagrams

State transition diagrams

State transition diagram

We can represent the hard-wired control device of a finite automaton by a directed multigraph:

• with the vertices representing the states
• arrow-edges being labelled by symbols of the input alphabet
• the initial state is marked by $>$
• the favourable states are double-circled
• each arrow represents a possible transition, hard-wired in the control device: an arrow from state $q$ to state $r$ labelled by symbol $a$ indicates that, when the head is reading $a$ and the control device is in state $q$ then it should move next to state $r$

Link to original

Automaton $A_1$

digraph {
	label=A₁
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	s->s [label=a]
	s->q [label=b]
	q->q [label=b]
	q->r [label=a]
	r->r [label=a]
	r->r [label=b]
}

Input 1: $abba$ Computation: $(s,abba),(s,bba),(q,ba),(q,a),(r,ϵ)$ $⇝$ word $abba$ is rejected

Input 2: $aabb$ Computation: $(s,aabb),(s,abb),(s,bb),(q,b),(q,ϵ)$ $⇝$ word $aabb$ is accepted

Input 3: $bbaaa$ Computation: $(s,bbaaa),(q,baaa),(q,aaa),(r,aa),(r,a),(r,ϵ)$ $⇝$ word $bbaaa$ is rejected

Input 4: $bbb$ Computation: $(s,bbb),(q,bb),(q,b),(q,ϵ)$ $⇝$ word $bbaaa$ is accepted

Input 5: $ϵ$ Computation: $(s,ϵ)$ $⇝$ word $bbaaa$ is rejected

Link to original

5. Deterministic Finite Automata

Deterministic Finite Automata

Deterministic Finite Automata

In order to describe a Deterministic Finite Automation, $\boxed{\text{DFA}}$, we describe 5 things:

• its states
• its input alphabet
• its (unique) initial state
• its favourable (or accepting) states there can be none, or more than one
• its transition function: for every (state, input symbol) pair we have to tell what the next state should be

A word $w$ is accepted by DFA $A$ if the computation of $A$ on input $w$ ends up in some favourable state. Otherwise, $w$ is rejected by $A$.

Link to original

What does ‘deterministic’ mean?

Taking this diagram from earlier:

digraph {
	label=A₁
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	s->s [label=a]
	s->q [label=b]
	q->q [label=b]
	q->r [label=a]
	r->r [label=a]
	r->r [label=b]
}

Deterministic means that for each state and symbol, there is a unique arrow coming out of the state labelled by the symbol.

As it is unique, there is one, but not more than one. We can say that, the pair $(\text{current state},\text{symbol read})$ uniquely determines the next state. This is why DFAs are called deterministic. DFAs will never “get stuck”, it never has to choose.

Transition Table

From $A_1$ above, we find that:

• States: $s,q,r$
• Input alphabet: $\{a,b\}$
• Initial state: $s$
• Favourable states: $q$

The transition table is another way of representing the transition function of $A_1$:

	$a$	$b$
$s$	$s$	$q$
$q$	$r$	$q$
$r$	$r$	$r$

For each cell in the table, there is a unique state to put in. As before, the pair uniquely indetifies the next state.

Link to original

6. Vending machine example

$A_2$: Vending machine example

digraph {
	label=A₂
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; 0;
	node[shape=circle];
	init->25
	
	25[label="s₂₅"]
	20[label="s₂₀"]
	15[label="s₁₅"]
	10[label="s₁₀"]
	5[label="s₅"]
	0[label="s₀"]
	
	25->20 [label="5p"]
	20->15 [label="5p"]
	15->10 [label="5p"]
	10->5 [label="5p"]
	5->0 [label="5p"]
	
	25->15 [label="10p"]
	20->10 [label="10p"]
	15->5 [label="10p"]
	10->0 [label="10p"]
	5->0 [label="10p"]
	
	25->5 [label="20p"]
	20->0 [label="20p"]
	15->0 [label="20p"]
	10->0 [label="20p"]
	5->0 [label="20p"]
}

For this diagram:

• states: $s_{25},s_{20},s_{15},s_{10},s_5,s_0$
• input alphabet: $\{5\text{p},10\text{p},20\text{p}\}$
• inital state: $s_{25}$
• favourable states: $s_0$

Word: any sequence of $5\text{p}$, $10\text{p}$ and $20\text{p}$ coins Accepts: all the words such that the sum of the coins is $\ge 25\text{p}$

Link to original

7. Language of a DFA

Language of a DFA

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

Language of a DFA

A DFA may accept certain words, while may reject others. If we collect all words accepted by a DFA $A$, we obtain a language: the language of a DFA $A$ is: ?

$$L(A)=\text{set of all words over its input alphabet that }A\text{ accepts}$$Link to original

Example

Using 4. State transition diagrams > Automaton A_1 (hover for preview), we already know:

• That $aabb$ and $bbb$ are accepted.
• That $abba$, $bbaaa$ and $ϵ$ were rejected.

Hence, $L(A_1)=\text{all the words starting with some (potentially none) }a\text{ s followed by at least one }b$.

$$\begin{array}{rl}L(A_1)& =\{a^n{b}^m|n=0,1,2,...,m=1,2,...\}\\ & =\{a^n{b}^m|n\in \mathbb{N},m\in {\mathbb{N}}^{+}\}\end{array}$$

Finding the language of a finite automaton

1. Experiment with words.
2. Come up with a language.
3. Test the suggested language:
   • every word that is accepted by the automaton should be in the suggested language
   • every word that is rejected by the automaton must not be in the suggested language
4. Revise the suggested language if necessary, then go to step 3.

Link to original

Transclude of 8.-some-more-examples