3
CHAPTER 2 COMPUTATIONAL MODELS(1)
• AUTOMATA •TURING MACHINES
4
CHAPTER 2
COMPUTATIONAL MODELS(1)
• AUTOMATA 1 FINITE AUTOMATA 1)DETERMINISTIC FINITE AUTOMATA(DFA) Example. An automatic door.
14
CHAPTER 2 COMPUTATIONAL MODELS(1)
DESIGNING FINITE AUTOMATA
0
0
1
qeven
qodd
1
How to design a DFA to recognize the language of all strings that contain the string 001 as a substring.
1 1
q1
0
0
0,1
q2
q3
q4
0
1
15
CHAPTER 2
COMPUTATIONAL MODELS(1)
THE REGULAR OPERATION Union: AB={x|xA or xB} Concatenation:AB={xy|xA and yB} Star:A*={x1x2xk|k0 and each xiA} EXAMPLE . A={good, bad}, B={boy, girl} AB=？ AB=？ A* =?
计算理论导引与算法复杂性
Introduction to the Theory of Computation and Algorithm Complexities
主讲：刘国华 （学院楼①225室，ghliu@）
助教：辛婷婷 （学院楼①153室，xtt.moon@）
FTP:222.204.215.3
3. : Q× Q is the transition function,
4. q0Q is the start state, and
12
5. F Q is the set of accept states.
CHAPTER 2 COMPUTATIONAL MODELS(1)
0
1
0,1
q1
q2
q3
front pad
rear pad
Rules for opening: 1 The door is closing, if some one is standing on the front pad (FRONT) and no one is standing on the rear pad (REAR) , then the door opens; 2 The door is opening, if some one is standing on the rear pad (REAR) , then the door keeps opening; 3 The door is opening, if some one is standing on the front pad and some one is standing on the rear pad (BOTH) , then the door keeps opening5;
1
CHAPTER 1 FUNDATION
6 BOOLEAN LOGIC
I’m sorry! 1)Negation 0=1, 1=0
2)Conjunction 01=0,11 =1 3)Disjunction 01=1 4)Exclusive or 00=0,01=1 5)Equality 00=1,1 0=0 6)Implication 10=0, 11=1,01=1,00=1 7)Distributive law P(QR)= (PQ)(PR) P(QR)= (PQ)(P R)
OPEN (d=1)
8
CHAPTER 2 COMPUTATIONAL MODELS(1)
front pad
rear pad
REAR BOTH NEITHER
CLOSED
FORNT NEITHER
FORNT REAR BOTH
OPEN
9
CHAPTER 2 COMPUTATIONAL MODELS(1)
练习题： 1 写出该状态图所表示DFA的形式化定义.
0,<RESET>
1,<RESET> 0
0
2
2,<RESET>
q1
q2
q3
1
1
2
2 给定一个语言A={w|w以1结束}，设计一个识别它的DFA.
19
16
}
CHAPTER 2
COMPUTATIONAL MODELS(1)
THEOREM 2.1 The class of regular languages is closed under the union operation. PROOF IDEA. A1=L(M1);A2=L(M2) A1A2=L(M3)?
Hoarwdwtoairmesp:letwmoenstenthsiosrsy; stem? one computer(only 1 bit memory), etc.
How about the software?
6
CHAPTER 2 COMPUTATIONAL MODELS(1)
satrt
tTRUE;d 0
NEITHER
FORNT REAR BOTH
OPEN
11
CHAPTER 2 COMPUTATIONAL MODELS(1)
0
1
0,1
q1
q2
q3
1
1
The state diagram for DFA M1
{1, , 11, 01, 001, 00001, , 01, 011, , 0011, , 00110}
1
1
The state diagram for DFA M1
1.Q ={q1, q2, q3},
2. ={0,1}, 3. is desribed as
01 q1 q1 q2 q2 q3 q2 q3 q2 q2
4. q1 is the start state, and
5. F={q2}.
13
CHAPTER 2 COMPUTATIONAL MODELS(1)
L(M)=A: Language of machine M, we say that M recoginizes A.
FORMAL DEFINITION OF COMPUTATION
Let M= (Q, , , q0,F) be a finite automaton and let w=w1w2wn be a string where each wi is a member of the alphabet . Then M accepts w if a sequence of states r0, r1,,rn in Q exists with
t=TRUE? Y N
end
s1sensor1 s2sensor2
d=1ands1=0ands2=0 N
Y d0
Y
d=0and(s2=1ors1=1ands2=1ors1=0ands2=0)
N
Y
d=1and(s1=1ors2=1ors1=1ands2=1)
N
Y
d=0ands1=1
N
d1
7
CHAPTER 2 COMPUTATIONAL MODELS(1)
CHAPTER 2 COMPUTATIONAL MODELS(1)
front pad
rear pad
Rules for closing: 1 The door is opening, if no one is standing on either pad (NEITHER), then the door closes; 2 The door is closing, if some one is standing on the rear pad (REAR) , then the door keeps closing; 3 The door is closing, if some one is standing on the front pad and some one is standing on the rear pad (BOTH) , then the door keeps closing.
front pad
rear pad
BOTH REAR NEITHER
CLOSED
FORNT NEITHER
FORNT BOTH REAR
OPEN
10
CHAPTER 2 COMPUTATIONAL MODELS(1)
front pad
rear pad
NEITHER CLOSED
FORNT REAR BOTH
three conditions: 1.r0=q0,
2. (r0, wi+1 )=ri+1, for i=0,,n-1, and
3.rnF. Regular language: a language is called a regular language if some finite automaton recognizes
front pad

rear pad
REAR
(s2=1)
BOTH
(s1=1ands2=1)
NEITHER
(s1=0ands2=0)
CLOSED (d=0)