Class Note for CMPSCI 601 at UMass(43)
Class Note for CMPSCI 601 at UMass(43)
Popular in Course
Popular in Department
This 16 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 14 views.
Reviews for Class Note for CMPSCI 601 at UMass(43)
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 3 Kleene s Theorem Let A Q 2 be any language 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 6 5 A is regular 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 CMPSCI 601 Recall From Last Time Lecture 3 Closure Theorem for Regular Sets Let A B Q 2 be regular languages and let h 23 gt F and g F gt 23 be homomorphisms Then the following languages are regular 1 AUB 2 AB 3 Z 23 A 4 AnB 5 MA 6 9 1A Proofs of Closure Properties Because we have so many equivalent models for the class of regular languages we can pick the one that makes each proof easiest Regular Expressions union concatenation star DFA complement hence intersection product of DFA s gives intersection directly ewNH forward homomorphism substitute into regexp or gen eral NFA U1 inverse homomorphism simulate on DFA 6 reversal see HWl Let h 2 gt A be a homomorphism If R is a regular expression over 2 we can compute MR inductively Then h R hR If M is a DFA with alphabet A and M A we can make a DFA for h 1A as follows States start and nal states are the same as M For every letter a in Z and every state q de ne 6q a to be 6340 ha Then for any 71 E 2 6qw 634qhw and 6q0w E F iff6j4q0 E F iffhw E A iffw E h 1A CMPSCI 601 Review Of C FL S Lecture 3 De nition A contextfree grammar CFG is a 4 tuple G V Z R S 0 V 2 variables nonterrninals 0 Z 2 terminals 0 R 2 rules productions R Q V X V U EDquot 0 S E V 0 V7 2 R are all nite G1 2 S7a7b7R178 R1 SaSbSe 3 aSbe S gt e S gt aSb gt ab S gt aSb gt aaSbb gt aabb S gt aSb gt aaSbb gt aaaSbbb gt aaabbb 501 w E 0va 1 52w anbn 1 neN 50 2 w e 23 1 311 G G2 E7T7F7KL7D7O777777y7z7071739quot797R27E E gt ETT L gt R T gt Tum D gt 01112119 2 F gt EVO C7 gt DOD V gt LD Parse Tree Pumping Lemma for Regular Sets Let D QZ6 1017 be a DFA Let n Let w E D st 2 n Then 329352 6 23 st the following all hold 0 vyz w 0 S n o gt 0 and Vic 2 macka 6 D Proof Let U E D st 2 7 By the Pigeonhole Principle 31239 lt jqi qj 71 711111239 wi1wj wj1wnu 10 1239 1239 If 6qhy 2 qt Thus xykz E D for all k E N A 8 Prop E arbr r E N is not regular Proof Suppose that E were regular accepted by a DFA with 7 states Let w 61 By pumping lemmaw anb xyz Where 0 S n 0 gt 0 and 0 We 6 Nvykz E E SinceO lt g n y 6120 lt 239 g n Thus 29302 2 can lb E E But all lb if E gtlt Therefore E is not regular A CFL Pumping Lemma Let A be a CFL Then there is a constant n depending only on A such that if z E A and z 2 n then there exist strings u v w 19 y such that 0 z uvwxy and 0 1213 2 1 and 12171129 3 n and for all k E N uvkka39g E A 10 proof Let G V 2312 S be a CFG with G A Let n be so large that for 2 n st Ngz for some N E V the parse tree for 3 has height gt W 2 Letz 6 142 7 The parse tree for 3 has height greater than V 2 Thus some path repeats a nonterminal N z uvwxy We 6 Nuvk kay E A 11 Prop P anbmanbm n m E N is not a CFL Proof Suppose P were a CFL Let n be constant of the pumping lemma Let 2 anbnanbn By pumping lemma 3 uvwxy and l 1019 2 l 2 12171129 3 n and 3 for all k E N uvkka39g E P Since 12mm 3 H mm 6 ab or mm 6 ba If either 2 or 19 contains both a s and 9 s then avg112292 is not in P Suppose that vac contains at least one a Then uv2wx2y is not in P because it has more a s in one group than the other Suppose that vac contains at least one I Then avg112292 is not in P because it has more US in one group than the other 2 Thus no 111292 is not in P gtlt Thus P is not a CFL A 12 Prop NONC FL anbncn n E N is not a CFL Proof The argument is almost identical We let 3 anbncn where n is larger than the constant given by the CFL Pumping Lemma So 3 uvwxy with 12171129 gt 0 12mm 3 n and uvlwxiy in NONC FL for all 239 Again neither 2 nor 1 can contain letters of two different types or avg112292 is not in abc But then avg112292 cannot contain equal numbers of a s 9 s and as as only one or two types of letter have been added A There are languages that are not CFL s but that still sat isfy the conclusion of the CFL Pumping Lemma On HW 1 you will prove one of these to be a nonCFL using closure properties 13 CMPSCI 601 Pushdown Automata PDA Lecture 3 De nition A pushdown automaton PDA is a 7 tuple P Q7 2 RA go 2017 0 Q nite set of states 0 Z 2 input alphabet 0 F stack alphabet 0 A g Q X 23 X I X Q X I nite set of transitions 0 go 6 Q start state 0 20 E F initial stack symbol 0 F Q Q nal states FDA 2 NFA stack 51 w 63 1 qoZogtqX7 JEF X 61 14 P1 qrsabABZoA1qZos A1 2 UL aa 67 17 Agt7 17 b7 67 17 Bgt7 17 67 67 r7 6 730714 7 6 7 573 7 6 7 67 20 87 gt aA aA A A bB bB 15 Theorem 31 Let A Q 23 be any language Then the following are equivalent 1 A Gf0r some CFG G 2 A Pf0r some PDA P 3 A is a contextfree language Proof See HMU or LP or S To prove 1 implies 2 we build a bottomup parser or topdown parser similar to those used in realworld compilers except that the latter are deterministic The proof that 2 implies l is of less practical interest it de nes languages like the strings that could take state 239 and empty stack to state 339 and empty stack and shows that these languages are interrelated by CFG rules A 16
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'