Class Note for CMPSCI 601 at UMass(32)
Class Note for CMPSCI 601 at UMass(32)
Popular in Course
Popular in Department
This 19 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 16 views.
Reviews for Class Note for CMPSCI 601 at UMass(32)
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 4 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 without 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 Regular Language Closure Lecture 4 Closure Theorem for Regular Sets Let A B Q 23 be regular languages and let h 23 gt F and g F gt 23 be homomorphisms Then the following languages are regular 1 A U B 2 AB 3 A 23 A 4 A n B 5 MA 6 9 1A A homomorphism of strings is a function 9 such that for any strings u and v guv gugv The set g 1A is de ned as u 9a E A 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 Forward homomorphism substitute into regexp or general NFA U1 Inverse homomorphism simulate on DFA 6 Reversal easy by regular expressions but also doable with NFA s exercise Let h 2 gt A be a homomorphism If R is a regular expression over Z we can compute a regular expression MR by induction on the de nition of regular expressions Then we can prove by induction that mm 50110 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 11 E 2 6q w 63401 hw and 6qow E F lt gt 534107hw E F H Mm E A lt gt w E h1A CMPSCI 601 Review Of C FL S Lecture 4 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 ltSaSbSe 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 2 anbn HEN 50 2 w e 23 1 311 G G2 E7T7F7xY7L7D7O777777y7z7071739quot797R27E 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 101 be a DFA Let n Let w E D st 2 n Then 329352 E 23 st the following all hold 0 vyz w 0 S n o gt 0 and 0 Vic 2 29ka E 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 We showed 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 the pumping lemmaw anbn xyz Where g ltn gt 0 and O Vic E Nvykz E E SinceO lt g n y 6120 lt 239 g n Thus 29302 2 can lb E E But all lb E 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 1a 2 n then there exist strings u v w 19 y such that 0 z uvwxy and a my 2 1 and 1mm 3 n and g for all k E N twigwacky 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 E 142 7 The parse tree for 3 has height greater than V 2 Thus some path repeats a nonterminal N z uvwxy We E Nuvkkay E A 11 Prop P anbmanbm n m E N is not a CFL Proof Suppose P were a CFL Let n be the constant of the CFL pumping lemma Let 2 anbnanbn By the CFL pumping lemma 3 uvwx39g and 1 my 2 l 2 1mm 3 n and 3 for all k E N wokwacky E P Since 11111229 3 H mm E ab or mm E ba If either 11 or 19 contains both a s and 9 s then avg112292 is not in P Suppose that 1119 contains at least one a Then avg112292 is not in P because it has more a s in one group than the other Suppose that 1119 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 2 uvwxy with 11mm gt 0 17171129 3 n and uvlwxiy in NONC FL for all 239 Again neither 1 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 13 Any CFL satis es the conclusion of the CFL Pumping Lemma but it is not true that any nonCFL must fail to satisfy it There are other tools that can show a language to be a nonCFL These include stronger forms of the Pumping Lemma and more closure properties Let EQUAL be the set of strings in a U I U e that have an equal number of a s 9 s and 0 s You can use the CFL Pumping Lemma on this with the right choice of 2 but far easier is using the fact that the intersection of EQUAL with abe is the language NONC FL If A is a CFL and R a regular language then A U R must be regular Proving this however requires a different characterization of the CFL s 14 CMPSCI 601 Pushdown Automata PDA S Lecture 4 De nition A pushdown automaton PDA is a 7 tuple P Q 2 RA go 2013 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 E 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 qEFyX EV 15 P1 qrsabABZgA1qZgs A1 ltq7 aa 67 17 Agt7 17 b7 67 17 Bgt7 17 67 67 r7 6 730714 7 6 7 573 7quot 6 7 67 Zn 87 gt aA aA A A bB bB 16 Theorem 41 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 We give only a sketch here there are detailed proofs in HMU LP and S To prove 1 implies 2 we can build a bottomup parser 0r topdown parser similar to those used in realworld compilers except that the latter are deterministic l7 The topdown parser is a PDA that 0 begins by pushing S onto its stack 0 may pop a terminal from the stack if can at the same time read a matching input letter 0 may execute a rule A gt w by popping A and pushing 711R 0 ends by popping the when done with the input The bottomup parser somewhat similarly pushes onto its stack 0 may transfer a terminal from the input to the stack 0 may execute A gt w by popping w and pushing A 0 ends by popping S when done 18 The proof that the language of any PDA is a CFL that 2 implies 1 is of less practical interest Given states 239 and 339 let Aij be the set of strings that could take the PDA from state 239 with empty stack to state 339 with empty stack If we can de ne rules making each Aij a CFL we win be cause the language of the PDA is the union of A5 for all nal states f where s is the start state So our grammar has a rule S gt A8 for each f We have all rules of the form Am gt Apr4m and a rule Am gt aArsb whenever moves of the PDA warrant it Here I am skipping some assumptions on the PDA and the nontrivial proof that any accepting run of the PDA corresponds to a valid derivation in our grammar A 19
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'