Finite Automata
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Finite Automata as PDF for free.
More details
- Words: 1,529
- Pages: 56
Finite Automata
1
Finite Automaton Input String
Finite Automaton
Output “Accept” or “Reject”
2
Transition Graph a, b
q5
b q0 a
a a b q1 b q2 b q3 a
initial state state
transition
a, b
q4 accepting state
3
Initial Configuration a b b a
Input String
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
4
Reading the Input a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
5
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
6
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
7
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
8
Input finished
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 accept 9
Rejection a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
10
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
11
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
12
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
13
Input finished
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
reject
a, b
q4
14
Another Rejection λ a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
15
λ a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
reject 16
Another Example a a b a, b
a
q0
b
q1
a, b
q2
17
a a b a, b
a
q0
b
q1
a, b
q2
18
a a b a, b
a
q0
b
q1
a, b
q2
19
a a b a, b
a
q0
b
q1
a, b
q2
20
Input finished
a a b a
q0
a, b
accept
b
q1
a, b
q2
21
Rejection Example b a b a, b
a
q0
b
q1
a, b
q2
22
b a b a, b
a
q0
b
q1
a, b
q2
23
b a b a, b
a
q0
b
q1
a, b
q2
24
b a b a, b
a
q0
b
q1
a, b
q2
25
Input finished
b a b a, b
a
q0
b
q1
a, b
q2 reject 26
Languages Accepted by FAs FA
M
Definition: The language L( M ) contains all input strings accepted by M
M L( M ) = { strings that bring to an accepting state} 27
Example
L( M ) = { abba}
M a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 accept 28
Example
L( M ) = { λ , ab, abba}
M a, b
q5
b
q0 a accept
a
a b q1 b q2 b q3 a accept
a, b
q4 accept 29
Example
L( M ) = {a b : n ≥ 0} n
a, b
a
q0
b
q1 accept
a, b
q2 trap state 30
Formal Definition Finite Automaton (FA)
M = ( Q, Σ, δ , q0 , F ) Q : set of states Σ : input alphabet
δ q0
: transition function
F
: set of accepting states
: initial state
31
Input Alphabet Σ
Σ = { a, b} a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 32
Set of States Q
Q = { q0 , q1, q2 , q3 , q4 , q5 } a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 33
Initial State q0
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
34
Set of Accepting States F
F = { q4 } a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
35
Transition Function δ
δ :Q×Σ → Q a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 36
δ ( q0 , a ) = q1 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 37
δ ( q0 , b ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 38
δ ( q2 , b ) = q3 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 39
δ q0 q1 q2 q3 q4 q5
a q1 q5
q5
q4 q5 q5
Transition Function δ
b q5 q2 q3 q5 q5 q5
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 40
Extended Transition Function δ *
δ * : Q × Σ* → Q a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 41
δ * ( q0 , ab ) = q2 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 42
δ * ( q0 , abba ) = q4 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 43
δ * ( q0 , abbbaa ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 44
Observation: if there is a walk from with label w then
q to q′
δ * ( q , w ) = q′
w
q
q′
w = σ 1σ 2 σ k q
σ1
σ2
σk
q′ 45
Example: There is a walk from q0 to q5 with label abbbaa
δ * ( q0 , abbbaa ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 46
Recursive Definition
δ * ( q, λ ) = q δ * ( q, wσ ) = δ (δ * (q, w),σ )
q
w
q1 σ
q′
δ * ( q , w σ ) = q′
δ (q1,σ ) = q′
δ * ( q, wσ ) = δ (q1,σ ) δ * ( q, w) = q1
δ * ( q, wσ ) = δ (δ * ( q, w),σ )
47
δ * ( q0 , ab ) =
δ ( δ * (q0 , a ), b ) =
δ ( δ ( δ * ( q0 , λ ), a ), b ) = δ ( δ ( q0 , a ), b ) = δ ( q1 , b ) = q2
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 48
Language Accepted by FAs For a FA
M = ( Q, Σ, δ , q0 , F )
Language accepted by
M
:
L( M ) = { w ∈ Σ* : δ * ( q0 , w) ∈ F } q0
w
q′
q′ ∈ F
49
Observation Language rejected by M :
L( M ) = { w ∈ Σ* : δ * ( q0 , w) ∉ F }
q0
w
q′
q′ ∉ F
50
Example
L( M ) = { all strings with prefix ab } a, b
q0
a
q1
b
a q3
b
q2 accept
a, b 51
Example L ( M ) = { all strings without substring 001 } 0
1
0,1
1
λ
0
0
00
1
001
0 52
Example
L( M ) = { awa : w ∈ { a, b} *}
a
b
q0
a
b q2
q3
a
b
q4 a, b
53
Regular Languages Definition: A language L is regular if there is FA M such that L = L( M )
Observation: All languages accepted by FAs form the family of regular languages 54
Examples of regular languages:
{ abba} { λ , ab, abba} { awa : w ∈ { a, b} *} {a nb : n ≥ 0} { all strings with prefix
ab }
{ all strings without substring 001 }
There exist automata that accept these Languages (see previous slides). 55
There exist languages which are not Regular: Example:
n n
L= {a b : n ≥ 0}
There is no FA that accepts such a language (we will prove this later in the class)
56
1
Finite Automaton Input String
Finite Automaton
Output “Accept” or “Reject”
2
Transition Graph a, b
q5
b q0 a
a a b q1 b q2 b q3 a
initial state state
transition
a, b
q4 accepting state
3
Initial Configuration a b b a
Input String
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
4
Reading the Input a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
5
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
6
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
7
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
8
Input finished
a b b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 accept 9
Rejection a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
10
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
11
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
12
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
13
Input finished
a b a a, b
q5
b q0 a
a a b q1 b q2 b q3 a
reject
a, b
q4
14
Another Rejection λ a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
15
λ a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
reject 16
Another Example a a b a, b
a
q0
b
q1
a, b
q2
17
a a b a, b
a
q0
b
q1
a, b
q2
18
a a b a, b
a
q0
b
q1
a, b
q2
19
a a b a, b
a
q0
b
q1
a, b
q2
20
Input finished
a a b a
q0
a, b
accept
b
q1
a, b
q2
21
Rejection Example b a b a, b
a
q0
b
q1
a, b
q2
22
b a b a, b
a
q0
b
q1
a, b
q2
23
b a b a, b
a
q0
b
q1
a, b
q2
24
b a b a, b
a
q0
b
q1
a, b
q2
25
Input finished
b a b a, b
a
q0
b
q1
a, b
q2 reject 26
Languages Accepted by FAs FA
M
Definition: The language L( M ) contains all input strings accepted by M
M L( M ) = { strings that bring to an accepting state} 27
Example
L( M ) = { abba}
M a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 accept 28
Example
L( M ) = { λ , ab, abba}
M a, b
q5
b
q0 a accept
a
a b q1 b q2 b q3 a accept
a, b
q4 accept 29
Example
L( M ) = {a b : n ≥ 0} n
a, b
a
q0
b
q1 accept
a, b
q2 trap state 30
Formal Definition Finite Automaton (FA)
M = ( Q, Σ, δ , q0 , F ) Q : set of states Σ : input alphabet
δ q0
: transition function
F
: set of accepting states
: initial state
31
Input Alphabet Σ
Σ = { a, b} a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 32
Set of States Q
Q = { q0 , q1, q2 , q3 , q4 , q5 } a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 33
Initial State q0
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
34
Set of Accepting States F
F = { q4 } a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4
35
Transition Function δ
δ :Q×Σ → Q a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 36
δ ( q0 , a ) = q1 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 37
δ ( q0 , b ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 38
δ ( q2 , b ) = q3 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 39
δ q0 q1 q2 q3 q4 q5
a q1 q5
q5
q4 q5 q5
Transition Function δ
b q5 q2 q3 q5 q5 q5
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 40
Extended Transition Function δ *
δ * : Q × Σ* → Q a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 41
δ * ( q0 , ab ) = q2 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 42
δ * ( q0 , abba ) = q4 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 43
δ * ( q0 , abbbaa ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 44
Observation: if there is a walk from with label w then
q to q′
δ * ( q , w ) = q′
w
q
q′
w = σ 1σ 2 σ k q
σ1
σ2
σk
q′ 45
Example: There is a walk from q0 to q5 with label abbbaa
δ * ( q0 , abbbaa ) = q5 a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 46
Recursive Definition
δ * ( q, λ ) = q δ * ( q, wσ ) = δ (δ * (q, w),σ )
q
w
q1 σ
q′
δ * ( q , w σ ) = q′
δ (q1,σ ) = q′
δ * ( q, wσ ) = δ (q1,σ ) δ * ( q, w) = q1
δ * ( q, wσ ) = δ (δ * ( q, w),σ )
47
δ * ( q0 , ab ) =
δ ( δ * (q0 , a ), b ) =
δ ( δ ( δ * ( q0 , λ ), a ), b ) = δ ( δ ( q0 , a ), b ) = δ ( q1 , b ) = q2
a, b
q5
b q0 a
a a b q1 b q2 b q3 a
a, b
q4 48
Language Accepted by FAs For a FA
M = ( Q, Σ, δ , q0 , F )
Language accepted by
M
:
L( M ) = { w ∈ Σ* : δ * ( q0 , w) ∈ F } q0
w
q′
q′ ∈ F
49
Observation Language rejected by M :
L( M ) = { w ∈ Σ* : δ * ( q0 , w) ∉ F }
q0
w
q′
q′ ∉ F
50
Example
L( M ) = { all strings with prefix ab } a, b
q0
a
q1
b
a q3
b
q2 accept
a, b 51
Example L ( M ) = { all strings without substring 001 } 0
1
0,1
1
λ
0
0
00
1
001
0 52
Example
L( M ) = { awa : w ∈ { a, b} *}
a
b
q0
a
b q2
q3
a
b
q4 a, b
53
Regular Languages Definition: A language L is regular if there is FA M such that L = L( M )
Observation: All languages accepted by FAs form the family of regular languages 54
Examples of regular languages:
{ abba} { λ , ab, abba} { awa : w ∈ { a, b} *} {a nb : n ≥ 0} { all strings with prefix
ab }
{ all strings without substring 001 }
There exist automata that accept these Languages (see previous slides). 55
There exist languages which are not Regular: Example:
n n
L= {a b : n ≥ 0}
There is no FA that accepts such a language (we will prove this later in the class)
56
Related Documents
Finite Automata
July 2020 6
Finite Automata
October 2019 20
Introduction To Finite Automata
October 2019 18
Finite Automata - Detailed
June 2020 25
Chapter Two: Finite Automata
May 2020 9