FIT2014 Theory of Computation Lecture 7 Finite Automata
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 7
Finite Automata
slides by Graham Farr
based in part on previous slides by David Albrecht
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 26
Overview
I Definition
I How they are used to define languages
I Representations
I Complement Languages
I Comparison with Regular Expressions
2 / 26
Finite Automaton (FA)
I Sometimes known as a Deterministic Finite Automaton (DFA).
I Used for determining whether a word does or does not belong to a Regular
Language.
I Used for defining a Regular Language.
I Used in Lexical Analysers.
3 / 26
Notation and terminology . . . and Alternative notation
a
b
a,bb
a
a
b
a,bb
a
states,
represented as vertices.
Special states:
I Start State
I Final State
transitions,
represented as directed edges,
labelled by letters
–
+
a
b
a,bb
a
4 / 26
Finite automaton: definition
I A finite set of states
I One called the Start State
I Some (maybe none) called Final States
I An alphabet of possible input letters
I A finite set of transitions
I that tell, for each state and each letter in the alphabet, which state to go to next.
I There is a unique transition from any state for each letter in the alphabet.
5 / 26
Finite automaton: representations
1
2
3
a
b
a,bb
a
a b
Start 1 1 2
2 3 3
Final 3 3 2
6 / 26
Finite automata
Every string traces a unique path in the automaton, starting from the Start State and
following the transitions, letter by letter.
7 / 26
1
2
3
a
b
a,bb
a
a b
Start 1 1 2
2 3 3
Final 3 3 2
8 / 26
Finite automata
Algorithm 1: Execution of a Finite Automaton
Input: a string
Begin at the Start State.
while there is another input letter do
Read the next letter of the input string.
Move along the directed edge labelled by this letter.
if you’re in a Final State then
Accept input string.
else
Reject input string.
9 / 26
Finite automata
Every string traces a unique path in the automaton, starting from the Start State and
following the transitions, letter by letter.
Definitions
A string is accepted by a FA if its path ends on a Final State.
Otherwise the string is rejected.
The language recognised by a FA is the set of all strings it accepts.
We say the FA recognises the language, or accepts the language.
10 / 26
Finite automata
1
2
3
a
b
a,bb
a
a b
Start 1 1 2
2 3 3
Final 3 3 2
11 / 26
1
2
3
4
5
a
b
ba ba
a
b
a
b
a b
Start 1 2 3
2 4 3
3 2 5
Final 4 4 5
Final 5 4 5
12 / 26
Special Cases
I All words accepted.
I No words accepted.
I Only the empty word accepted.
I Only non-empty words accepted.
I A single word accepted.
13 / 26
Complements
If L is a language over an alphabet, then its complement L is the set of words over
the alphabet that are not in L.
L = Σ∗ \ L
The complement of L is sometimes denoted by L′ or Lc .
Examples
∅ = Σ∗ Σ∗ = ∅ {words of ≤ 3 letters} = {words of ≥ 4 letters}
EVEN-EVEN := { strings that contain an even number of a’s and an even number of b’s }
= { ε, aa, bb, aaaa, aabb, abab, abba, baab, . . . }.
EVEN-EVEN := { strings which contain an odd number of a’s or an odd number of b’s }
= { a, b, ab, ba, aaa, aab, aba, abb, baa, . . . }
14 / 26
EVEN-EVEN
b
b
aa aa
b
b
15 / 26
Complement Finite Automaton (FA)
Suppose some FA accepts the language L.
Change all the final states in this FA to non-final states,
and all the non-final states to final states.
This new FA now accepts all the strings not accepted by the original FA
(i.e., all the words in L),
and rejects all the words that the original accepted
(i.e., the words in L).
So the new FA accepts L.
16 / 26
EVEN-EVEN
b
b
aa aa
b
b
17 / 26
Comparison with Regular Expressions
It is (usually) easier
to write down a regular expression that defines a language
than
to design a FA to accept this language.
It is easier
to check whether a given string is accepted by a FA
than
to see whether it matches a regular expression.
It is easier
to find complements using a FA
than
by using a regular expression.
18 / 26
Some Generalizations of Finite Automata
This week:
I It is not required that, for every state and letter, there is a unique transition.
I It can change state without reading a letter.
I It can read more than one letter at a time.
Next week:
I It can read strings which match regular expressions, not just single letters.
Later:
I Each transition can produce output letters as well as changing state. (transducer)
I Transitions can read and write letters from some kind of memory.
I For a given state and letter, the next state is chosen probabilistically.
19 / 26
Nondeterministic Finite Automaton (NFA)
NFA are defined like a Finite Automaton (FA) except for transitions.
Transitions
I For some states and letters there is a transition.
I The labels may include the empty word ε.
So for a given letter and state there may be:
I No transition
I More than one transition
For a given string, the path it takes . . .
I might not exist
I might not be unique
20 / 26
aba
a b a
b
a b
a,b
a,b
FA
sink state
a b a
NFA
21 / 26
ab ∪ abb ∪ baa
a b b
a
b
b
a a
22 / 26
Is abbbabbbabba accepted?
a a,b
a
bb
aa
b
a
b
a b
a
b
23 / 26
Properties
I If there is no transition for the current letter and state the machine crashes.
I Paths from the Start State to a Final State for a given input:
I One
I None
I Several (Nondeterministic)
I Accept a string if there is at least one path from the Start State to a Final State.
I Reject a string if there are no paths from the Start State to a Final State.
24 / 26
a(aa ∪ bb)∗b
a ε
a
b
a
b
ε b
ε
ε
25 / 26
Revision
Finite Automata (FA)
I Definition. How to use them.
I How to construct a Finite Automaton to accept a language.
Complement Languages
I What they are. Designing FA to accept them.
Nondeterministic Finite Automata (NFA)
I Definition. How to use them
I How to construct a Nondeterministic Finite Automaton to accept a language.
Reading: Sipser Ch 1.
26 / 26