### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(43)

### View Full Document

## 14

## 0

## 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.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(43)

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.