Complexity and Computability Theory I Lecture #3 Rina Zviel-Girshin Leah Epstein Winter 2002-2003 Overview Finite automata Deterministic automata Regular languages Regular operations Nondeterminism Rina Zviel-Girshin @ASC 2 FA vs. computer • Both a finite automaton (or a finite-state machine) and a real computer have a "central processing unit" of a fixed, finite capacity. • This is a common property of them both. • A FA delivers no output at all. • A FA is a language recognition device. • A FA is a restricted model of real computers with no memory apart from the fixed central processor. Rina Zviel-Girshin @ASC 3 Deterministic finite automata • A finite automaton is called deterministic if for each in and each qj in Q there exist a unique (qj,)=qk. qj qk Example: qj ? qj Rina Zviel-Girshin @ASC qk qi 4 Extended transition function • Notation: ’ • ’: Q*Q • The extended transition function ’ defines the computation of an automaton on word w= u. • Formal definition ’(q,u)= (’(q,u), )=m Rina Zviel-Girshin @ASC 5 Example u q k m where ’(q,u)= (’(q,u), )= (k, )= m Rina Zviel-Girshin @ASC 6 Language recognition • Let A=(Q,,,q0,F) be a finite automaton and w=12...n a string over *. A accepts w if there exists a sequence of states r0,r1,..rn in Q with the following properties: 1. r0 = q0 2. (ri, i+1) = ri+1 for i=0,1,..n 3. rn F • We say A recognizes language L if L = {w| A accepts w}. Rina Zviel-Girshin @ASC 7 Regular language • A language is called “a regular language” if some finite automaton recognizes it. • Notation: R • The class of languages accepted by finite automata is identical to the class of regular languages. Rina Zviel-Girshin @ASC 8 Example is regular. q0 Rina Zviel-Girshin @ASC 9 Example * is regular. q0 Rina Zviel-Girshin @ASC 10 Example L={} is regular. q0 q1 Rina Zviel-Girshin @ASC 11 Example For each α in the language Lα = {α} is regular. q0 q1 q2 Rina Zviel-Girshin @ASC 12 Regular operations Union Intersection Complement Minus Concatenation Rina Zviel-Girshin @ASC 13 Union Theorem: The class of regular languages is closed under the union operation. If L1 and L2 are regular, so is L1L2. Basic idea: •proof by construction: construct an automaton M that uses the automaton A of L1 and the automaton B of L2 and works by simulating both A and B. Rina Zviel-Girshin @ASC 14 How can M simulate A and B? • M could run w on A and if A accepts then M accepts. • Or it could run w on B and if B accepts then M accepts. But • if w not accepted by A? • We can't rewind the input tape. • Once the letter is used the is no way back. Rina Zviel-Girshin @ASC 15 Simulator Another approach: • We simulate A and B simultaneously. • To do so we need to remember the current states of both machines. • M will have states in QA QB. qa,qb Rina Zviel-Girshin @ASC 16 Formal proof Let A recognize L1 where A = (QA, , A, q0A, FA) and B recognize L2 where B = (QB, , B, q0B, FB) . Construct M to recognize L1 L2, where M = ( Q, , , q0, F). 1. Q={ (rA,rB) | rA in QA and rB in QB}. 2. is the same for both A and B. Otherwise let construct = AB 3. is defined as follows: for each (rA,rB) in Q and in , let ((rA,rB),)=(A(rA,),B(rB,)). Rina Zviel-Girshin @ASC 17 Formal proof 4. q0 is a pair (q0A,q0B) 5. F is the set of pairs in which at least one member is an accept state of A or B. F = { (rA,rB) | rA in FA or rB in FB} or F = (FAQB)(QAFB). This concludes the construction of the finite automaton M that recognizes the union of L1 and L2. Rina Zviel-Girshin @ASC 18 Formal proof • Now we have to prove that L(M)= L1 L2. To prove the equality we have to prove that: • L1 L2 L(M). and • L(M) L1 L2. Rina Zviel-Girshin @ASC 19 L1 L2 L(M). • If x L1 L2 then x L1or x L2 • That means: ’A(q0A,x)=rA Fa or ’B(q0B,x))= rB FB • So ’(q0,x)= ’((q0A,q0B),x)= (’A(q0A,x), ’B(q0B,x)) = (rA,rB) where (rA,rB) (FAQB) or (rA,rB) (QAFB). • By definition of F: ’(q0,x)=(rA,rB) (FAQB)(QAFB)=F • That means x L(M). Rina Zviel-Girshin @ASC 20 L(M) L1 L2 • If xL(M) then ’(q0,x)= ’((q0A,q0B),x)= (’A(q0A,x), ’B(q0B,x)) F • By definition of F: (’A(q0A,x), ’B(q0B,x))F means ’A(q0A,x) FA or ’B(q0B,x)) FB • So x belongs to L1or to L2. • By definition of union: x L1 L2 • That means L(M) L1 L2. Rina Zviel-Girshin @ASC 21 Intersection Theorem: The class of regular languages is closed under the intersection operation. If L1 and L2 are regular, so is L1L2. Basic idea: • proof by construction: construct an automaton M that uses the automaton A of L1 and the automaton B of L2 and works by simulating both A and B. Rina Zviel-Girshin @ASC 22 Formal proof Let A recognize L1 where A = (QA, , A, q0A, FA) and B recognize L2 where B = (QB, , B, q0B, FB) . Construct M to recognize L1 L2, where M = ( Q, , , q0, F). 1. Q={ (rA,rB) | rA in QA and rB in QB}. 2. is the same for both A and B. Otherwise let construct = A B 3. is defined as follows: for each (rA,rB) in Q and in , let ((rA,rB),)=(A(rA,),B(rB,)). Rina Zviel-Girshin @ASC 23 Formal proof 4. q0 is a pair (q0A,q0B) 5. F is the set of pairs in which each member is an accept state of A or B (respectively). F = { (rA,rB) | rA in FA and rB in FB} or F = FAFB. That concludes the construction of the finite automaton M that recognizes intersection of L1 and L2. Rina Zviel-Girshin @ASC 24 Correctness • To prove the correctness of the construction algorithm in a formal way we need to prove that • L(M)L(A) L(B) and • L(A) L(B)L(M). Rina Zviel-Girshin @ASC 25 L(M)L(A) L(B) • Let w* and wL(M) ’(q0,w)=’((q0A,q0B),w)=(’A(q0A,w),’B(q0B,w)) if wL(M) then ’(q0,w)=’((q0A,q0B),w)F (’A(q0A,w),’B(q0B,w))F=(FAFB) ’A(q0A,w)FA and ’B(q0B,w)FB means wL(A) and wL(B) wL(A)L(B) L(M)L(A) L(B). Q.E.D. Rina Zviel-Girshin @ASC 26 L(A) L(B)L(M) • Let w* and w L(A) L(B) wL(A) and wL(B) ’A(q0A,w)FA and ’B(q0B,w)FB ’(q0,w)=’((q0A,q0B),w)=(’A(q0A,w),’B(q0B, w))(FAFB)=F means wL(M) L(A) L(B)L(M). Q.E.D. Rina Zviel-Girshin @ASC 27 Complement Theorem: The class of regular languages is closed under the complement operation. If L is regular, so is “not L” (the complement language of L). Basic idea: • proof by construction: construct an automaton M that uses the automaton A of L and rejects all words A accepts and vice versa. Rina Zviel-Girshin @ASC 28 Formal proof Let A recognize L where A = (QA, , A, q0A, FA) . Construct M to recognize L, where M = ( Q, , , q0, F). 1. Q= QA 2. = A 3. is defined as follows: for each rA in Q and in , let (rA, )=A(rA,) 4. q0 =q0A 5. F = { rA | rA not in FA } or F = QA - FA. Rina Zviel-Girshin @ASC 29 The set minus operation Theorem: The class of regular languages is closed under the minus operation. If L1 and L2 are regular, so is L1-L2. Formal proof: L1-L2 = L1(notL2) Rina Zviel-Girshin @ASC 30 Concatenation Theorem: The class of regular languages is closed under the concatenation operation. If L1 and L2 are regular, so is L1L2. Rina Zviel-Girshin @ASC 31 Concatenation Basic idea: • To construct M we need to break a word w into two pieces u and v and check if u is in L1 and v is in L2. • But how to break an input into the pieces? • To solve this problem we need to use a new approach called nondeterminism. Rina Zviel-Girshin @ASC 32 Nondeterminism • In a nondeterministic machine several "next states" are possible. • The automaton may choose any of these legal next states. qj qk qi Rina Zviel-Girshin @ASC 33 Nondeterminism • It also allows to change a current state without reading an input. qj qk This situation called an - transition Rina Zviel-Girshin @ASC 34 DFA vs. NFA • Every deterministic finite automaton DFA is immediately a nondeterministic finite automaton NFA. • The opposite is not true. Rina Zviel-Girshin @ASC 35 Example • Construct a nondeterministic finite automaton for the following language: L = { w1 | w over *={0,1}*} q0 q1 0,1 Rina Zviel-Girshin @ASC 36 Any Questions? • More about non-determinism on next lecture. Rina Zviel-Girshin @ASC 37

Descargar
# Complexity and Computability Theory I