Class Note for CMPSCI 601 at UMass(12)
Class Note for CMPSCI 601 at UMass(12)
Popular in Course
Popular in Department
This 26 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(12)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 3 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 In formal language theory we look at various kinds of machines that take a string as input look at one letter at a time and decide whether the string is in some language We also look at various formal ways to speci a lan guage such as regular expressions and contextfree gram mars that are used in the real world In the 1950 s and 1960 s it was discovered that each of the most natural machine models corresponded to a spec i cation system the languages that could be decided by the machines were exactly those that could be speci ed in a certain way Here we ll see some examples of that phenomenon Finally we will always be interested in when a language cannot be decided by any machine in some class or can not be Speci ed within some system Such a result is called a lower bound because we show that some partic ular amount of resources is insuf cient CMPSCI601 Regular Expressions and Sets Lecture3 De nition The set of regular expressions RE over alphabet E is the set of strings made up from E e and 0 and using the operations U o and Meaning of a Regular Expression 1 ifa E 2 then a E RE a a 2 e E RE 6 e 3 D E RE 03 2 D 4 ife f E RE then so are e U f e o f 8 Me U f 18 U f 6 0 f 8 f W l u E 138 E f 1 8 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 Q Q is the set of nal or accept states A DFA executes the following pseudoJava algorithm public boolean isAccepted String w State 5 startState for int i0 i lt wlength i s deltas wcharAti return isFinalStates We will be interested in the following results about DFA s and regular languages 0 Kleene s Theorem A language is decided by some DFA iff it is regular 0 MyhillNerode Theorem There is a minimal DFA for any regular language de nable in terms of a purely languagetheoretic property 0 NonRegularity Proofs If a language is not regular we can usually prove that fact 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 Q Q is the set of nal or accept states MN 71113ng17 So Aq a is the set of states to which N might go if it reads a when in state q There might be zero one or more than one Proposition 31 Every NFA N can be translated into an NFA without etransitions N39 such that N N39 Proposition 32 For every NFA N with n states there is a DFA D with at most 2 states st D N Theorem 33 Kleene s Theorem Let A Q 2 be any language Then the following are equivalent 1 A Df0r some DFA D 2 A Nf0r some NFA N with no etransitions 3 A Nf0r some NFA N 4 A e for some regular expression e 5 A is regular Proof Obvious that 1 gt 2 gt 3 3 gt 2 by Prop 12 eelimination 2 gt 1 by Prop 13 subset construction 4 lt gt 5 by de nition 4 gt 3 We showed by induction on all regular expres sions e that there is an NFA N with e N 3 gt 4 Cf state elimination proof 8 Lemma 132 LetN 1nEA1FF f1fr Lg E w j E Aiw n0 intermediate state gt k L9 a1jEAiCL u 6121 1 k1 k k k k Lii sz U Lik1Lk1k1 Lk1j k L kI kI CMPSCI 601 The Myhill Nerode Theorem Lecture 3 Let A Q 2 be any language De ne the rightequivalence relation NA 0n 2 chy 42gt VwEEcwEA lt gt waA 1 NA 3 iff 1 and 3 cannot be distinguished by concate nating some string 11 t0 the right of each of them and testing for membership in A Example A1 w 6 ab 4711 E 0m0d2 ewAlawAlaa bwabwbbb Claim 19 NAl y iff 42 E 79253 mod 2 Proof Suppose 1 NAl y Let w e cwzrcEAl lt gt ywyEA1 Thus 1129 E 79253 mod 2 Suppose 455 E by mod 2 Vwbcw E byw mod 2 Vwcw 6 A1 lt gt gm 6 A1 Thus 1 NAl g Q 1211 wez1um 111 w 6 a7 51 1 512121 1111 w 6 a7 51 1 11111 0 mod 2 1 mod 2 10 Review Show that for any language A NA is an equiv alence relation Recall that an equivalence relation is a binary relation that is re exive symmetric and transi tive Proof Re exive V51 6 251 NA 19 Let 29111 E 2 be arbitrary cwEl lt gt Ierl V11 6 25011 E A lt gt 2911 E A because 11 was arbitrary chrc V51 6 251 NA 19 because 1 was arbitrary ll Symmetric V5134 E 229 NA y gt y NA 19 Let 51931 6 2 be arbitrary Suppose 1 NA y VwcwEA lt gt yw EA Vwyw A lt gt 2971 EA ZINAIC Ay gtyAfIJ Way 6 WW NA 2 gt 9 NA 50 12 Transitive Vzcyz E Ec NAyAy NA z gtc NA z Let 19 y z E 2 be arbitrary Suppose 1 NA y y NA z Vwcw E A lt gt gm 6 A Vwyw E A lt gt zw E A Let w E 2 be arbitrary cwEA lt gt waA waA lt gt szA cwEA lt gt szA V11 6 22911 E A lt gt zw E A because 11 was arbitrary QCNAZ NAyJNAZ gtAZ Vrcyz E 251 NA 3 y NA z gt 1 NA zbecause 19 y z were arbitrary Q 13 CMPSCI 601 Recall These Proof Methods Lecture 3 0 To prove V5090 let 1 be arbitrary prove 0 conclude V5090 To prove 0 gt 20 assume 0 prove 20 conclude 0 gt 20 c From 0 20 may conclude 0 20 0 From 0 20 may conclude 0 20 0 To prove 0 assume 10 prove A A conclude 0 l4 An Example Sc M41 9 ltgt 451 E 4 mOd 2 b This language has two equivalence classes and the DFA operates by reading each letter in turn and determining the class of the part of the string seen so far The cor respondence between states and classes is the essence of the theorem 15 MyhillNerode Theorem The language A is regular iff NA has a nite number k of equivalence classes Fur thermore this number k is equal to the number of states in the minimumstate DFA that decides A Proof Suppose A D for some DFA D q17q27 39 39 39 7qn7 2 67 ql Let Si w I 5917711 I 9239 Claim Each Si is contained in a single NA equivalence class Let 1 y 6 5239 w E 2 be arbitrary 5q17 W 55q17 50 w 55q17 y w 5q1 yw MD Z l 011726 F rm 6 A lt gt 6q11w6 F lt gt 6q1yw E F lt gt gm 6 A Vwcw E A lt gt gm 6 A QCNAy Thus there are at most n equivalence classes 16 Conversely suppose that there are nitely many equiva lence classes of NA E1 Em Let be the equivalence class that 1 is in De ne D 2 El Em 26 6 F where F 519 1 it E A 5056 a M We must show that 6 is well de ned ie 50 9 gt lival Lyell Suppose 1 NA y Vwcw E A lt gt gm 6 A Vwmw E A lt gt yaw E A Thus 5m NA ya Claim 6ec Proof by induction on exercise E D lt gt 6ecEF lt gt MEF lt gt 2961 17 Example The following language is regular and its minimal DFA has seven states A7 wE019 1 7w D7 016E670 67q d 10g d mod 7 2 3g d mod 7 It is straightforward to show that D7 A7 try this as an exercise To show that D7 is minimal we must show that there are seven different equivalence classes Since the strings 0 1 6 each take D7 to a different state they are our candidates to be in different classes We must show W 7 E 07177690 74AM 18 Let 239 7A j 6 01 6 be arbitrary We can nd a number d such that 3239 d E 0 mod 7 why If 239 NA j were true then we would have 3339 d E 0mod 7 because 6id would have to equal 6jd But in that case 3id E 3jdmod7 3239 E 3339 mod 7 15239 E 15339 mod 7 239 E j mod 7 Thus we must have 239 794 j Since 239 and 3 were arbitrary no two of the seven strings are equivalent and there are seven classes 19 CMPSCI601 Proving Languages NonRegular Lecture3 By Kleene a language is nonregular if it has no DFA By MyhillNerode then A is nonregular if NA has in nitely many equivalence classes To prove that A is nonregular we nd an in nite set of strings no two of which are VAequivalent Example Show E 2 WW n E N is not regular Proof Letz 3A 3 E N be arbitrary We can easily show from the de nition that CL 7 aj Let w bl alw E E ajw e E So each element of al 239 E N is in a separate equiva lence class 20 Another Example PAL 2 w w 2113 is not regular Here MB is w written backwards It s almost true that no two different strings are equiva lent but not quite Can you nd a counterexample All we need for the proof though is to nd an in nite set of strings oib 239 E N is such a set if there are two distinct letters a and b in 2 What if 2 contains only a single letter This is called a unary language Then PAL is a regular language why It s easy to miss cases like this if you re not care ll But look at our proof In order to nish it we had to assume that there were two different letters in E To justify this step we must add a condition to the statement of the problem Harder Example The set U PRIME de ned as oi 239 is prime is not regular 21 CMPSCI 601 Regular Language Closure Lecture 3 We have seen that a single class of formal languages has several alternate speci cations by Kleene s Theorem a language has a DFA iff it has an NFA iff it has a regular expression There are more This suggests that this class has mathematical importance The alternate characterizations are also useful in proofs For example we can ask what operations when applied to regular languages always give us more regular lan guages Cases of this phenomonon are called closure properties 22 Closure Theorem for Regular Sets Let A B Q 2 be regular languages and let h 2 gt I and g I gt 2 be homomorphisms Then the following languages are regular 1 AUB 2 AB 3 2i 2 A 4 A B 5 MA 6 9 1A The last two require a new de nition A language homomorphism is a function h 2 gt F St Way 6 TXMW hhy 33 23 Examples h 0123 gt ab M0 2 cm M1 1 M2 aba M3 e h012310 aabababaa g ab gt abc 9a a 95 2 cbc gbaa cbcaa Notation for function f A gt B sets 539 Q A T Q B 1 W 1 a6 5 f 1T a 6A 1 fun ET Example A1 w 6 ab 50111 E 0m0d2 h391A1 w E 0123 1w 2011 E 0m0d 2 9A1 w E a b c 656 E 0 mod 2 no otherb or c 24 Proofs of Closure Properties 12 Let e A f B Thus eUf AUB eof AB 3 Let D A DFA D Q 2 6 s F Let QE6 8Q Thus L15 2 Z myAmBZuF 5 Let A e Thus MA he Example 9a a7 95 050 A ababa gA acbcacbca 25 6 Let A D DFA D Q 2 6 s F Let D QF6 8F 539q 7 5q7 717 Example MO 2 cm M1 b h2 aba M3 e D a g a 12 0 3 D 0 3 a 12 26