Transcript `b` or

Deterministic
Finite Automata
And Regular Languages
1
Deterministic Finite State Automata (DFA)
2
Deterministic Finite State Automata (DFA)
3
Deterministic Finite State Automata (DFA)
4
Deterministic Finite Automaton (DFA)
Input Tape
String
Finite
Automaton
Output
“Accept”
or
“Reject”
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
6
Alphabet
  {a , b }
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
For every state, there is a transition
for every symbol in the alphabet
7
head
Initial Configuration
a b b a
Input Tape
Input String
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
Initial state
8
Scanning the Input
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
9
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
10
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
11
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
12
A Rejection Case
a b a
Input String
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
13
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
14
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
15
Input finished
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
reject
a, b
q4
16
Another Rejection Case
Tape is empty
( )
Input Finished
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
reject
17
Language Accepted:
L  abba 
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
18
To accept a string:
all the input string is scanned
and the last state is accepting
To reject a string:
all the input string is scanned
and the last state is non-accepting
19
Another Example
L   , ab, abba
a, b
q5
b
q0 a
Accept
state
a
a
b
q1 b q2 b q3 a
Accept
state
a, b
q4
Accept
state
20
Empty Tape
( )
Input Finished
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
accept
21
Formal Definition of a DFA
•
A DFA is a five-tuple:
M = (Q, Σ, δ, q0, F)
Q
Σ
q0
F
δ
A finite set of states
A finite input alphabet
The initial/starting state, q0 is in Q
A set of final/accepting states, which is a subset of Q
A transition function, which is a total function from Q x Σ to Q
δ: (Q x Σ) –> Q
δ(q,s) = q’
δ is defined for any q in Q and s in Σ, and
is equal to some state q’ in Q, could be q’=q
Intuitively, δ(q,s) is the state entered by M after reading symbol s while in
state q.
22
• Example #1:
1
Q = {q0, q1}
Σ = {0, 1}
Start state is q0
F = {q0}
0
q1
q0
1
0
δ:
q0
0
q1
1
q0
q1
q0
q1
23
• Example #2:
a
Q = {q0, q1, q2}
Σ = {a, b, c}
Start state is q0
F = {q2}
δ:
q0
b
q0
a
q0
b
q0
c
q1
q1
q1
q1
q2
q2
q2
q2
q2
a,b,c
a
c
q1
c
q2
b
• Since δ is a function, at each step M has exactly one option.
• It follows that for a given string, there is exactly one computation.
24
Transition Function
 :Q  Q
 (q , x )  q 
q
x
q
Describes the result of a transition
from state q with symbol x
25
Definitions related to DFAs
•
Let M = (Q, Σ, δ,q0,F) be a DFA and let w be in Σ*. Then w is accepted by M
iff δ(q0,w) = p for some state p in F.
•
Let M = (Q, Σ, δ,q0,F) be a DFA. Then the language accepted by M is the
set:
L(M) = {w | w is in Σ* and δ(q0,w) is in F}
•
Another equivalent definition:
L(M) = {w | w is in Σ* and w is accepted by M}
•
Let L be a language. Then L is a regular language iff there exists a DFA M
such that L = L(M).
•
Let M1 = (Q1, Σ1, δ1, q0, F1) and M2 = (Q2, Σ2, δ2, p0, F2) be DFAs. Then M1
and M2 are equivalent iff L(M1) = L(M2).
26
•
Notes:
– A DFA M = (Q, Σ, δ,q0,F) partitions the set Σ* into two sets: L(M) and
Σ* - L(M).
– If L = L(M) then L is a subset of L(M) and L(M) is a subset of L (def. of set
equality).
– Similarly, if L(M1) = L(M2) then L(M1) is a subset of L(M2) and L(M2) is a subset
of L(M1).
– Some languages are regular, others are not. For example, if
Regular: L1 = {x | x is a string of 0's and 1's containing an even
number of 1's} and
Not-regular: L2 = {x | x = 0n1n for some n >= 0}
•
Can you write a program to “simulate” a given DFA, or any arbitrary input DFA?
•
Question we will address later:
– How do we determine whether or not a given language is regular?
27
• Give a DFA M such that:
L(M) = {x | x is a string of 0’s and 1’s and |x| >= 2}
0,1
q0
0,1
q1
0,1
q2
28
• Give a DFA M such that:
L(M) = {x | x is a string of (zero or more) a’s, b’s and c’s such
that x does not contain the substring aa}
b,c
a,b,c
a
q0
q1
a
q2
b,c
Logic:
In Start state (q0): b’s and c’s: ignore – stay in same state
q0 is also “accept” state
First ‘a’ appears: get ready (q1) to reject
But followed by a ‘b’ or ‘c’: go back to start state q0
When second ‘a’ appears after the “ready” state: go to reject state q2
Ignore everything after getting to the “reject” state q2
29
• Give a DFA M such that:
L(M) = {x | x is a string of a’s, b’s and c’s such that x
contains the substring aba}
b,c
a
a
q0
c
q1
a,b,c
b
a
q2
q3
b,c
Logic: acceptance is straight forward, progressing on each expected
symbol
However, rejection needs special care, in each state (for DFA, we will see
this becomes easier in NFA, non-deterministic machine)
30
• Give a DFA M such that:
L(M) = {x | x is a string of a’s and b’s such that x
contains both aa and bb}
First do, for a language where ‘aa’ comes before ‘bb’
Then do its reverse; and then parallelize them.
a
b
a
q1
q2
q3
b
a,b
a
a
q0
a
q7
b
b
b
q4
b
a
q5
b
q6
a
Remember, you may have multiple “final” states, but only one “start”
state
31
• Let Σ = {0, 1}. Give DFAs for {}, {ε}, Σ*, and Σ+.
For {ε}:
For {}:
0,1
0,1
q0
q0
For Σ*:
0,1
q1
For Σ+:
0,1
0,1
q0
q0
0,1
q1
32
Special case:
for any state q
 q,    q
*
33
In general:
 q ,w   q 
*
implies that there is a walk of transitions
w   1 2  k
q
1
k
2
q
states may be repeated
q
w
q
34
For a DFA
M  Q, ,  , q0 , F 
Language accepted by

M:
L M   w   :  q0 ,w   F
q0
*
w
*
q

q  F
35
Language rejected by

M:
LM   w   :  q0 ,w   F
q0
*
w
*
q

q  F
36
  {a , b }
LM = { all strings with prefix ab }
a, b
q0
a
q1
b
a
q3
b
q2
accept
a, b
37
LM  = { all binary strings containing
substring 001 }
0,1
0
1
1

0
0
00
1
001
0
38
LM  = { all binary strings without
substring 001 }
0
1
0,1
1

0
0
00
1
001
0
39

L(M )  awa : w  a , b 
*
b

a
b
q0
a
q2
q3
a
b
q4
a, b
40
Regular Languages
Definition:
A language L is regular if there is
a DFA M that accepts it ( L(M )  L )
The languages accepted by all DFAs
form the family of regular languages
41
Regular Operations on Languages
Let A and B be languages.
Union : A  B  {x | x  A or x  B}.
Concatenat ion : A  B  {xy | x  A and y  B}.
Star : A  {x1 x2  xk | k  0 and each xi  A}.
*
The first two operations are binary operations ,
and the last one a unary operation.
42
Example 1.11
Let the alphabet  be {a, b,, z}.
Let A  {good, bad} and B  {boy, girl }. Then, we have
A  B  {good, bad, boy, girl },
A  B  {goodboy, goodgirl, badboy, badgirl }, and
A*  { , good, bad, goodgood, goodbad, badbad,
goodgoodgo od, good goodbad, goodbadgoo d,
goodbadbad , }.
43
Theorem 1.12 Closedness for Union
The class of regular languages is closed under
the union operation.
In other word s, if A1 and A2 are regular languages,
so is A1  A2 .
44
Proof of Theorem 1.12
Let M 1 recognize A1 , where M 1  (Q1 , , 1 , q1 , F1 ),
and M 2 recognize A2 , where M 2  (Q2 , ,  2 , q2 , F2 ).
Construct M to recognize A1  A2 ,
where M  (Q, ,  , q, F ).
Then, check the correctnes s of the constructi on.
Proof of Th 1.12
45
Construction of M
1. Q  Q1  Q2  {( r1 , r2 ) | r1  Q1 and r2  Q2 }.
2. We can assume that M 1 and M 2 have the same
alphabet . (Why?)
3. (r1 , r2 )  Q, a  ;  (( r1 , r2 ), a)  (1 (r1 , a ),  2 (r2 , a ))
4. q0  (q1 , q2 ).
5. F  ( F1  Q2 )  (Q1  F2 )  {( r1 , r2 ) | r1  F1 or r2  F2 }.
Proof of Th 1.12
46
Correctness
You should check the following.
1. For any string recognized by M1 is
recognized by M.
2. For any string recognized by M2 is
recognized by M.
3. For any string recognized by M is
recognized by M1 or M2.
Proof of Th 1.12
47
Theorem 1.13 Closedness for
concatenation
The class of regular languages is closed under concatenat ion
operation. In other word s, if A1 and A2 are regular languages,
so is A1  A2 .
48
Nondeterminism
• To prove Theorem 1.13, we need
nondeterminism.
• Nondeterminism is a generalization of
determinism. So, every deterministic
automaton is automatically a
nondeterministic automaton.
49
50
• Problem: Third symbol from last is 1
0,1
q0
1
q1
0,1
q2
0,1
q3
Is this a DFA?
No, but it is a Non-deterministic Finite Automaton
51