Class Note for CMPSCI 601 at UMass(50)
Class Note for CMPSCI 601 at UMass(50)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for CMPSCI 601 at UMass(50)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI601 Introduction Lecture 1 Indepth introduction to main models concepts of theory of computation 0 Computability what can be computed in principle 0 Logic how can we express our requirements 0 Complexity what can be computed in practice Concrete Mathematical Problem Formal Models of Computation Finitestate 0 Stacks CFL Turing Machine 0 Logical Formula CMSPSCI 601 Requirements Lecture 1 Texts available at Jeffery Amherst College Store P Christos Papadimitriou Computational C omplex 17 BE Jon Barwise and John Etchemendy Language Proof and Logic Prerequisites Mathematical maturity reason abstractly understand and write proofs CMPSCI 250 needed CMPSCI 3 11 401 helpful Today s material is a good taste of the sort of stuff we will do Work 0 eight problem sets 35 of grade c midterm 30 of grade c nal 35 of grade Cooperation Students should talk to each other and help each other but write up solutions on your own in your own words Sharing or copying a solution could result in failure If a signi cant part of one of your solutions is due to someone else or some thing you ve read then you must acknowledge your source CMSPCI 601 On Reserve in Dubois Library Lecturel Mathematical Sophistication 0 How to Read andDo Proofs Second Edition by Daniel Solow 1990 John Wiley and Sons Review of Regular and ContextFree Languages 0 Hopcroft Motwani and Jeffrey D U11manIntroa uc tion to Automata Theory Languages and Computa tion 2001 Chapters 1 6 0 Lewis and Papadimitriou Elements of the Theory of Computation 1998 Chapters 1 3 0 Sipser Introduction to the Theory of Computation 1997 Chapters 1 2 NP Completeness 0 Garey and Johnson Computers and Intractability 1979 Descriptive Complexity 0 Immerman Descriptive Complexity 1999 3 Syllabus will be up soon on the course web site 0 httpwwwcs umass edu barring08601 There is a pointer there to the Spring 2002 web site and the syllabus there will be close to what we do here Rough guide 0 Formal Languages and Computability 9 lectures 0 Propositional and FirstOrder Logic 7 lectures 0 Complexity Theory 11 lectures CMPSCI 601 Review Of Regular Sets Lecturel De nition An alphabet is a nonempty nite set eg E 01 F abc etc De nition A string over an alphabet E is a nite sequence of zero or more symbols from E The unique string with zero symbols is called 6 The set of all strings over 2 is called 2 De nition A language over 2 is any subset of 2 The decision problem for a language L is to input a string 11 and determine whether 11 E L De nition The set of regular expressions 122 over alphabet E is the smallest set of strings such that l ifa E Ethena E RE 2 e E RE 3 I E RE 4 if e f 6 122 then so are the following a 8 U f b 8 0 f C 6 Examples 0 81 0 E R01 0 82 a U 7 o a U b E Ra 7 0 83 ababa E Ra b 0 Meanings 0 60000304 0i 1 iEN O an2 w 6 ab E 0m0d2 39 ababa w 6 MW 1 120111 E 0m0d2 Recall the meaning of Kleene star for any set A A E ii Ai i0 2 AouAluAguo E eUAUay 3yEAU E 1332n nEN1nEA Meaning of a Regular Expression 1 ifa E 2 then a 6 122 3a a 2 e E RE 6 e 3 7 E RE EUD 7 4 ife f 6 122 then so are e U f e o f 8 178 U f 178 U EU 178 O f 81709 W 1 u E 8771 E Em 175 8 De nition 11 A C 2 is regular iff 38 E REA 8 In other words a set A is regular iff there exists a regular expression that denotes it De nition A deterministic nite automaton DFA is a tuple DQE6SF 0 Q is a nite set of states 0 E is a nite alphabet 0 6 Q X E gt Q is the transition function 0 s E Q is the start state and 0 F C Q is the set of nal or accept states D1 S7q7a7b7617878 61 ltltS7agt78gt7ltlt87bgt7Qgt7ltltQ7agt7Qgt7ltltQ7bgt78gt 9 Cl a V 1 D1 w 6 ab 110112 E 0m0d2 1 ababa De nition A nondeterministic nite automaton NFA is a tuple N QEA3F 0 Q is a nite set of states 0 E is a nite alphabet 0 A Q X E U gt 50Q is the transition function 0 s E Q is the start state and 0 F C Q is the set of nal or accept states MN w 1 SinF 505 2 powersetofS A1AQS 10 Nn QOw o 39 7Qn170717Amq7Qn1 An ltltQO7Ogt7QOgt7 ltltQO71gt7QO791gt739 39 39 7 ltltQn71gt7Qn1gt You will Show in HW 1 that to accept Nn a DFA would need 2quot1 states 11 Proposition 12 Every NFA N can be translated into an NFA w0 etransitl39ons N39 SJ N N39 Proof GivenN QEAQOF16 ENQ727AI7907FI where A39qar38tq gt81gtt gtr F39 q 1 386396 38 12 Notation For a DFA D Q E 6 s F let 6q 11 be the state that D will be in after reading string 21 when started in q V0176 E q 5 27 wa E 505 27 w a D E w 6sw E F For an NFA without 6 transitions N Q 215 sF let Aq 11 be the set of states that N can be in after reading string 11 when started in q NUM 9 AV wa 2 U Ana 2 gt WM lt gt N E w Asw F7E 13 Proposition 13 For every NFA N with n states there is a DFA D with at most 2 states st D N Proof Let N QEA 1017 By Proposition 12 may assume that N has no 6 transitions Let D we 2 6 90 F 6Sa U Ara TEES F395 Q1SOF7 14 Claim For all 71 E 2 5 m7 w NMoW By induction on 17111203 5QO 10 AVG076 1w k1 wzua Inductively 6QO7 u N020 u WHQoLW 55qo7u7 a U AUquot a r 5q0u U A 7quot a TEAq0u Aq ua Therefore D N 15 Theorem 14 Kleene s Th Let A C 2 be any lan guage Then the following are equivalent 1 A Df0r some DFA D 2 A Nf0r some NFA N WO 6 transitions 3 A Nf0r some NFA N 4 A e for some regular expression e 5 A is regular Proof Obvious that l gt 2 gt 3 3 gt 2 by Prop 12 2 gt 1 by Prop 13 subset construction 4 lt gt 5 by def of regular 4 gt 3 We show by induction on the number of symbols in the regular expression e that there is an NFA N with e N e 80 e gt 16 II to Union C oncatenation LNLN1LN2 LNLN1LN2 N1 Kleene Star LltNgt ltLltN1gt N 17 3e4LaNz rwnLEA ij ww E w j E A22w n0 intermediate state 7 gt k L9 a1jEAiQ U 517Zj 1 k1 k k k k L Lij U Lik1Lk1k1 Lk1j k L kI kI 18
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'