Class Note for CMPSCI 601 at UMass(24)
Class Note for CMPSCI 601 at UMass(24)
Popular in Course
Popular in Department
This 22 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 11 views.
Reviews for Class Note for CMPSCI 601 at UMass(24)
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
CMPSCI 601 Recall From Last Time Lecture 2 De nitions 0 An alphabet is a nonempty nite set eg E 0 1 etc 0 The set of regular expressions 122 over alphabet E 0 A language is regular iff it is denoted by some regular expression 0 A DFA is atuple D Q E 6 s 0 An NFA is atuple N Q 215 s Prop 12 Every NFA N can be translated into an NFA N which has the same number of states but no etransitions st N N 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 2 W2 2 6 C10 F 6Sa U Ara TEES F395 QISHF7 01 096 01 Claim For all 71 E 2 5CIow NUMW By induction on 17111203 5 10 10 1561076 1212 k1 wzua Inductively 5 107 u N010 u 5 107Ua 55 102U7a U AU a T 5q0u U AU a TEAQ0U Aqua Therefore D N Theorem 14 Kleene s Th Let A g 2 be any lan guage Then the following are equivalent 1 A D for some DFA D 2 A N for some NFA N wo 6 transitions 3 A N for some NFA N 4 A e for some regular expression 8 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 8 that there is an NFA N with 8 N e 80 e o H m Union C oncatenation LNLN1LN2 LNLN1LN2 N1 Kleene Star LltNgt ltLltN1gt N 1 3e4LaNz rwnLEA ij ww If E w I j E Aiw n0 intermediate state gt k ajEAMHLJinj 1 k1 k k k at k sz sz U Lik1Lk1k1 Lk1j k L kI kI Let A g 2 be any language De ne the rightequivalence relation NA 0n 2 chy 42gt VwEEwEi lt gt waA 1 NA y iff 1 and y 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 I 4712 E 0m0d2 ewAlawAlaa bwabwbbb Claim 19 A1 y iff 42 E 79253 mod 2 Proof Suppose 1 A1 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 A1 y um wez1um a w 6 MY 1 4212 b w 6 MY 1 471 0 mod 2 1 mod 2 Exercise Show that for any language A NA is an equivalence relation Recall that an equivalence relation is a binary relation that is re exive symmetric and tran sitive 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 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 258 NA 2 gt 9 NA 50 10 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 11 CMPSCI 601 Some Proof Methods Lecture 2 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 0 From 0 20 may conclude 0 20 0 From 0 2p may conclude 0 20 0 To prove 0 assume 10 prove A A conclude 0 12 Sc M41 9 ltgt 451 E 4 mOd 2 13 MyhillNerode Theorem The language A is regular iff NA has a nite number of equivalence classes Fur thermore this number of equivalence classes is equal to the number of states in the minimumstate DFA that ac cepts A Proof Suppose A D for some DFA D QI7 C127 39 7g 7 E7 67 C117 Let Si 2 w I 5C117 w 2 C12 Claim Each Si contained in single NA equivalence class Let 1 y 6 5239 w E 2 be arbitrary 59117 5m 57579117 M7711 575791179 w V0117 21w 139 Z l Nam E F 5w 6 A lt gt 6q1517w6 F lt gt 6q1yw E F lt gt gm 6 A Vwcw E A lt gt gm 6 A 1 NA y Thus there are at most n equivalence classes 14 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 E 6 e F where F 56 I 56 E A 5050 a M Must show that 6 is well de ned ie 58 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 6 c Proof by induction on exercise E D lt gt 6ecEF lt gt MEF lt gt 2961 15 Example Prove that the following language is regular and its minimal DFA has seven states A7 7116 019 I 71711 D7 016E670 67q d 2 NC dmod 7 2 3g dmod 7 Must show D7 A7 exercise and W 75339 E Oilww l i 74471 Letz 74339 6 01 6 be arbitrary Pick d st 3239 d E 0mod 7 Suppose 3339 d E 0rnod 7 3id E 3jdmod7 3239 E 3339 mod 7 15239 E 15339 mod 7 239 E 339 mod 7 gtlt l6 ThusiodEA7jod A7i74A7j 17 Example ShowE a b I n E N is not regular pf Letz 75 j E N be arbitrary We will show that ai 75E aj Let w bi aim E E aj w Z E Thus NE has in nitely many equivalence classes Thus by the MyhillNerode Theorem E is not regular 18 A language homomorphism is a function h 2 gt I St Vim E 2htvy hrvhy 20 Examples h 0123 gt ab M0 2 an M1 7 M2 aba M3 e M012310 aabababaa g ab gt abc 9a a Cbc gbaa cbcaa Notation for function f A gt B sets 5 Q A T g B f0 a I CLES f1T CLEA I 1 ET Example A1 w 6 ab I 50111 E 0mod2 h1A1 w E O123 I 1w 2w E 0mod 2 MA w E a b c I 656 E 0 mod 2 no otherb or c 19 Closure Theorem for Regular Sets Let A B lt 2 be regular languages and let h 2 gt I and g I gt 2 be homomorphisms Then the following languages are regular 1 AU B 2 AB 321 2 A 4 A B 5mm 69 1A Proof 12 Let e A f B Thus eUf AUB eof AB 3 Let D A DFA D Q 2 6 s F LetB Q26 8Q Thus B Z myAmBZu 20 5 Let A e Thus MA he Example 9a a Cbc A ababa gA acbcacbca 21 6 Let A 30 DFA D Q 2 6 s F Let D QF6 8F Wm 5q7 717 Example MO 2 cm M1 b h2 aba M3 e D a g a 12 0 3 D 0 3 a 12 22
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'