Deterministic Finite Automata
COMP1600 / COMP6260
Australian National University
Semester 2, 2020
The Story So Far …
Logic.
language and proofs to speak about systems precisely useful to express properties and do proofs
Functional Programs
establish properties of functional programs main tool: (structural) induction
Imperative Programs.
again: focus on properties of programs main tool: Hoare Logic
Q. Is there a general notion of computation? That encompasses both?
1/42
First Shot: Your Laptop
Abstract Characteristics.
can do computation
has memory – a finite amount has (lots of) internal states
2/42
From Laptops to Formal Models
Concrete (your laptop) realistic (it exists!)
complex
hard to analyse
Abstract (mathematical model) exists only as a model simple
easy to analyse
Q. What is a “good” simple model of computation?
should match what really exists (possibly by a long shot) should be conceptually simple
3/42
First Answer: Finite State Automata
Basic Components.
internal states – finitely many
state transitions – triggered by reading input simplifying assumption: just one output: yes/no
Data.
basic input: strings (what you type in, text/xml file) characters: drawn from finite set (alphabet)
4/42
Example: Java Identifiers
From Oracle’s Java Language Specification.
An identifier is a sequence of one or more characters. The first character must be a valid first character (letter, $, ) in an identifier of the Java programming language, hereafter in this chapter called simply “Java”. Each subsequent character in the sequence must be a valid nonfirst character (letter, digit, $, ) in a Java identifier.
Graphical Specification
Identifier $ _
Letter
Letter
Digit
$ _
Q. Can you “see” a machine that recognises Java identifiers?
5/42
Java Identifiers
Example: Main Components
Letter Identifier $
_
Letter
Digit $ _
Data.
drawn form a finite alphabet (unicode, or ASCII)
Control.
“yes” if I can get from the left to the right, “no” otherwise have states after taking a transition (implicit in diagram)
Computational Problem with yes/no answer:
it a given sequence of characters a valid Java identifier?
6/42
Preview.
Next two weeks. Finite Automata
start with simplest model: finite automata relate to regular languages, non-determinism conclusion: finite automata “too simple”
The week after. Pushdown automata
like finite automata, but some more memory
useful for e.g. specifying syntax of programming languages still “too simple” for general computation
Then. Turing machines
The most widely accepted model of computation
infinite memory
idea: buy another hard disk whenever your computation runs out of memory
limits of what can be computed
7/42
Finite State Automata: First Example
The simplest useful abstraction of a “computing machine” consists of: A fixed, finite set of states
A transition relation over the states
Example: a traffic light FSA has 3 states:
-G R
G names state in which light is green. Y names state in which light is yellow. R names state in which light is red.
@
R@
Y
System designs are often in terms of state machines.
8/42
Second Example: Vending Machine
Operation
accept 10c and 20c coins
delivers if it has received at least 40c and selection is made
– 0c – 20c – 40c
select
20 20
select
10 10 10
R@ 10 @R 10 @R
@ @ @
10c 20 -30c 20 -50c
Note.
transitions are labelled
new ingredient: final states (doubly circled)
Computation. Sequences of actions (labels) from initial to final state.
9/42
Language Examples
Main Idea.
input: a string over a fixed character set operation: transitions labelled with characters output: yes if in final state after reading the input
More Generally.
Setup: Fix a finite set of characters (an alphabet)
Problem: A set of strings (called language) that are “valid” or “good” Task: decide computationally which strings are “good”
Example Languages.
1. A finite set.
2. Palindromes consisting of bits (0,1):
{0, 1, 00, 11, 010, 101, 000, 111, 0110, …} Languages in this sense are called formal languages.
{a, aa, ab, aaa, aab, aba, abb}
10/42
Terminology
Alphabet.
A finite set (of symbols). Usually denoted by Σ.
Strings over an alphabet Σ
finite sequence of characters (elements of Σ), can be the empty
sequence. E.g. for Σ = {a, b, c}, ababc is a string over Σ. Languages over alphabet Σ
are just sets of strings over Σ.
Sentences of the language
just another name for the elements (strings) of the language.
Notation:
Σ∗ is the set of all strings over Σ.
Therefore, every language with alphabet Σ is some subset of Σ∗.
11/42
Automata
First Model of Computation. Deterministic Finite Automata solve computational problem: given string s, is s accepted?
Basic Ingredients. (see e.g. traffic light and vending machine example) The alphabet of a DFA is a finite set of input tokens that an
automaton acts on.
a DFA consists of a finite set of states (a primitive notion)
One of the states is the initial state — where the automaton starts At least one of the states is a final state
A transition function (next state function):
State×Token → State
12/42
Recurring Theme
Diagrammatic Notation.
useful for humans
e.g. the transition diagram of the vending machine
Mathematical Notation.
useful for formal manipulation (e.g. proving theorems) useful for computer implementation
Glue between Diagrams and Maths
both notions convey precisely the same information crucial: being able to switch back and forth!
13/42
Formal Definition of DFA
A Deterministic Finite State Automaton (DFA) consists of five parts: A = (Σ,S,s0,F,N)
an input alphabet Σ, the set of tokens
a set of states S
an “initial” state s0 ∈ S (we start here)
a set of “final” states F ⊆ S (we hope to finish in one of these) atransitionfunction N:S×Σ → S
Aside. Having a transition function is what makes the automaton deterministic.
14/42
Finite State Automata as String Acceptors
Idea. A finite state automaton
works on strings over an alphabet Σ
determines which strings in Σ are “good” (accepted) and which strings are “bad” (rejected)
Acceptance Informally. Let A = (Σ,S,s0,F,N) be a DFA. Then A accepts the string w = a1a2 . . . an if there is a sequence of states
a1 a2 an−1 an
s0 −→s1 −→…−→sn−1 −→sn
a where s0 is the starting state, sn ∈ F is an accepting state, and s −→ t if
δ(s,a) = t.
Informally. Run the automaton from the starting state, move states according to the individual letters of the word, and accept if you end up in a final state.
15/42
Example 1
As a diagram.
1
– S0 S2
0
S 1 0
Alphabet – {0,1}
States – {S0,S1,S2}
Initial state – S0
Final states – {S2}
Transition function (as a table) –
In Mathematical Notation.
1 @ 10 6
R@
01
S0 S1 S0 S1 S1 S2 S2 S1 S0
Q1. Which strings are accepted by this automaton? Q2. What changes if we re-name the states?
16/42
Example 1, ctd
Recall. N : S × Σ → S is the transition function. 01
S0 S1 S0 S1 S1 S2 S2 S1 S0
Single Steps of the automaton
N(S0,0) is the state that the automation transitions to from state S0
reading letter 0.
Here: N(S0,0) = S1.
Multiple Steps of the automaton
N(N(S0,0), 1) is the state of the automation when starting in S0 and
reading first 0, then 1. Here: N(N(S0, 0), 1) = S2.
17/42
Example 2
b a,b,c abc – U – V
→U Z V Y
@ b ⊙V V V V
? a,b,cR@ c
@ YZVY
-Za Y ⊙ZZZZ
(the table carries the same information as the diagram) Q. What is the language of this automaton?
18/42
Eventual State Function
Revisit example 1:
1
– S0 S2
0
1 @ 10 6
@R
S 1 0
Input 0101 takes the DFA from S0 to S2, Input 1011 takes the DFA from S1 to S0, etc
A complete list of such possibilities is a function from a given state and a string to an ‘eventual state.’
This is the idea of Eventual State Function.
19/42
Eventual State Function — Definition
Definition. Let A be a DFA with states S, alphabet Σ, and transition function N.
The eventual state function for A is of type N∗ : S × Σ∗ → S
and is defined inductively by:
N∗(s,ε) = s (N1) N∗(s,xα) = N∗(N(s,x),α) (N2)
Or in Haskell, where strings are lists of elements of type Sigma
% n :: State -> Sigma -> State — given
nstar :: State -> [Sigma] -> State
nstar s [] = s
nstar s (a:as) = nstar (n s a) as
Informally. N∗(s,w) is the state A reached by starting in state s and reading string w.
20/42
An Important (but Unsurprising) Theorem about N∗
Theorem. For all states s ∈ S and for all strings α, β ∈ Σ∗ N∗(s,αβ) = N∗(N∗(s,α),β)
Proof by induction on the length of α. Base case: α = ε
LHS = N∗(s, εβ) = N∗(s, β) RHS = N∗(N∗(s, ε), β)
= N∗(s,β) = LHS
(by (N1))
21/42
Proof ctd: Step case:
Step Case. Show that N∗(s, (xα)β) = N∗(N∗(s, xα), β)
LHS = N∗(s, (xα)β) = N∗(s,x(αβ))
= N∗(N(s,x),αβ)
= N∗(N∗(N(s, x), α), β)
RHS = N∗(N∗(s, xα), β)
= N∗(N∗(N(s, x), α), β)
Corollary — when β is a single token
N∗(s,αy) = N(N∗(s,α),y)
(by (N2)) (by IH)
(by (N2))
22/42
Example
1
– S0 S2
0
1 @ 10 6
@R
S 1 0
N∗(S1, 1011) = N∗(N(S1, 1), 011) = N∗(S2,011)
= N∗(S1,11) = N∗(S2,1) = N∗(S0,ε) = S0
23/42
Language of an Automaton, Revisited
Acceptance, with eventual states. Let A = (Σ,S,s0,F,N) be an DFA and w be a string in Σ∗.
Then w is accepted by A if
N∗(s0,w) ∈ F
Q1. How does this compare with the earlier notion of acceptance? Q2. How can we prove that both are equivalent?
24/42
Example 1 again
1
– S0 S2
0
1 @ 10 A: 6
1
S 1 0
Q. Which strings are accepted?
e.g. 0011101 takes the machine from state S0 through states S1, S1,
S2, S0, S0, S1 to S2 (a final state).
N∗(S0, 0011101) = N∗(S1, 011101) = N∗(S1, 11101) =
…N∗(S1,1) = S2
others: 01, 001, 101, 0001, 0101, 00101101 . . .
25/42
Example 1 (ctd.)
1
– S0 S2
0
1 @ 10 A: 6
S 1 0
Accepted Strings.
01, 001, 101, 0001, 0101, 00101101 . . .
Strings that are not accepted.
ε, 0, 1, 00, 10, 11, 100 . . .
Q. What do the accepted strings have in common? How do we justify this?
1
26/42
Proving an Acceptance Predicate — in General
Our Claim. The automaton A accepts precisely the strings that are elements of the language L = {w ∈ Σ∗ | P(w)}.
(P is sometimes called an acceptance predicate.)
Proof Obligations.
1. Show that any string satisfying P is accepted by A. 2. Show any string accepted by A satisfies P.
27/42
Proving an Acceptance Predicate for A1
Proof obligation 1:
If a string ends in 01, then it is accepted by A1. That is: For all α ∈ Σ∗, N∗(S0,α01) ∈ F
Proof obligation 2:
If a string is accepted by A1, then it ends in 01. That is: Forallw∈Σ∗,ifN∗(S0,w)∈Fthen ∃α∈Σ∗. w=α01
28/42
Part 1: ∀α ∈ Σ∗, N∗(S0, α01) ∈ F Lemma:
Proof by cases:
∀s ∈ S. N∗(s,01) = S2
N∗(S0, 01) = N∗(S1, 1) = S2 N∗(S1, 01) = N∗(S1, 1) = S2 N∗(S2, 01) = N∗(S1, 1) = S2
So, by the “append” theorem above,
N∗(S0, α01) = N∗(N∗(S0, α), 01) = S2
29/42
Part2: N∗(S0,w)=S2 =⇒ ∃α. w=α01 Proof. Suppose N∗(S0,αxy) = S2.
By corollary to append-theorem (case of single token): N(N∗(S0, αx), y) = S2
By the definition of N, y must be 1 and N∗(S0,αx) must be S1. Similarly,
N(N∗(S0, α), x) = S1 and x is 0, again by the definition of N.
30/42
Another Example
What language does this DFA accept?
SOB:
– S0 – S1 – S2 1 1 1
0 0 0 666
31/42
Answer for SOB
SOB accepts the language of bitstrings containing exactly one 1-bit. Proof obligations:
Show that if a bitstring contains exactly one 1-bit then it is accepted by SOB.
Show that if a string is accepted by SOB it contains exactly one
1-bit.
SOB:
– S0 – S1 – S2 1 1 1
0 0 0
666
32/42
Mapping to Mathematics
Expressed mathematically, the main conclusion is L(SOB)={w∈Σ∗ |w=0n10m}
The two subgoals are
1. Ifw=0n10m thenN∗(S0,w)=S1 2. If N∗(S0,w) = S1 then w = 0n10m.
For this DFA the phrase “w is accepted by SOB” is captured by the expression N∗(S0,w)=S1.
33/42
Proving these subgoals
The first subgoal follows immediately from the following two lemmas, which are easily proved by induction:
Lemma 1: ∀n ≥ 0. N∗(S0, 0n) = S0 Lemma 2: ∀n ≥ 0. N∗(S1, 0n) = S1
Therefore
N∗(S0, 0n10m)
=N∗(N∗(S0, 0n), 10m) =N∗(S0, 10m) =N∗(N(S0, 1), 0m) =N∗(S1, 0m)
(by apppend Theorem) (by Lemma 1) (by def. N∗) (by def. N) (by Lemma 2)
∀w: N∗(S0,w)=S1 =⇒ ∃n,m≥0.w=0n10m can be proved in a similar fashion to Example 1 on earlier slides.
=S1
The second subgoal, stated more formally as
34 / 42
Limitations of FSAs
Q. Is an FSA a “good” model of computation?
Suppose we have a program P that always terminates
and outputs “yes” or “no” for every input string
Is there an FSA that accepts precisely the strings for which P says “yes”?
Technical Analysis. Properties of languages accepted by a DFA.
A very important example: L = { anbn | n ∈ N}
L = {ε,ab,aabb,aaabbb,a4b4,a5b5,…}
Claim. There is no FSA that recognises this language.
(because an FSA’s memory is limited.)
Q. Given the claim above, are FSA’s realistic models of computation?
35/42
Proof of Claim
Proof by contradiction.
Suppose A is an FSA that accepts L. That is L = L(A). Then each of the following are states of A:
N∗(S0,a), N∗(S0,a2), N∗(S0,a3) …
But A only has finitely many states, so some state must repeat:
There are distinct i and j such that N∗(S0, ai ) = N∗(S0, aj ). that is, the automaton cannot tell ai and aj apart.
36/42
Proof by contradiction (ctd)
Since ai bi is accepted, we know
N∗(S0,aibi) ∈ F
By the append theorem
N∗(N∗(S0,ai),bi) = N∗(S0,aibi) ∈ F
Now, since N∗(S0, ai ) = N∗(S0, aj )
N∗(N∗(S0,aj),bi) = N∗(S0,ajbi) ∈ F
So ajbi is accepted by A but ajbi is not in L, contradicting the initial assumption.
37/42
Pigeon-Hole Principle
The proof used the pigeon-hole principle:
No function from one set to a smaller finite set can be one-to-one.
••
••
(Finiteness is not really necessary — no function from one set to another with smaller cardinality can be one-to-one.)
“You cannot fit n + 1 pigeons into n holes”
••
•
38/42
Equivalence of Automata
Two automata are said to be equivalent if they accept the same language.
?0 ?0
S 1 S0 S -0-1 -0
Example:
A4: 6 1 A5: 61 11
? ?
000 -S31 S2 S1
Q. Can FSAs be simplified? is there an equivalent FSA with fewer states?
39/42
Equivalence of States
Two states Sj and Sk of an FSA are equivalent if, for all input strings w N∗(Sj,w) ∈ F if and only if N∗(Sk,w) ∈ F
Example. In A4, S2 is equivalent to S0 and S1 is equivalent to S3.
?0
S 1 S0 -0 -1
A4: 6 1 1
?
00
– S 3 1 S 2
40/42
Elimination of Equivalent States
Assumptions.
A = (Σ,S,S0,F,N) is an FSA
Sk and Sj be equivalent
Sk ̸= S0 (don’t eliminate the initial state!)
Elimination of Sk from A: new automaton A′ = (Σ,S′,S0,F′,N′) S′ is S without Sk
F′ is F without Sk
N′(s,w) = (if N(s,w) = Sk then Sj else N(s,w))
41/42
Example
Since S2 ≡ S0 in A4 , let’s eliminate S2 . Newsetofstatesis {S0,S1,S3}
New set of final states is {S0}
New transition function is:
?0
1-0
– S0 S1 0 1
1
A6: 61 S0S0S1 S1 S1 S0
0 SSS -S3 330
42/42