### 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(50)

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Department

This 18 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.

## Similar to Course at UMass

## Popular in Subject

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

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

CMPSCI601 Introduction Lecture 1 Indepth introduction to main models concepts of theory of computation 0 Computability what can be computed in principle 0 Logic how can we express our requirements 0 Complexity what can be computed in practice Concrete Mathematical Problem Formal Models of Computation Finitestate 0 Stacks CFL Turing Machine 0 Logical Formula CMSPSCI 601 Requirements Lecture 1 Texts available at Jeffery Amherst College Store P Christos Papadimitriou Computational C omplex 17 BE Jon Barwise and John Etchemendy Language Proof and Logic Prerequisites Mathematical maturity reason abstractly understand and write proofs CMPSCI 250 needed CMPSCI 3 11 401 helpful Today s material is a good taste of the sort of stuff we will do Work 0 eight problem sets 35 of grade c midterm 30 of grade c nal 35 of grade Cooperation Students should talk to each other and help each other but write up solutions on your own in your own words Sharing or copying a solution could result in failure If a signi cant part of one of your solutions is due to someone else or some thing you ve read then you must acknowledge your source CMSPCI 601 On Reserve in Dubois Library Lecturel Mathematical Sophistication 0 How to Read andDo Proofs Second Edition by Daniel Solow 1990 John Wiley and Sons Review of Regular and ContextFree Languages 0 Hopcroft Motwani and Jeffrey D U11manIntroa uc tion to Automata Theory Languages and Computa tion 2001 Chapters 1 6 0 Lewis and Papadimitriou Elements of the Theory of Computation 1998 Chapters 1 3 0 Sipser Introduction to the Theory of Computation 1997 Chapters 1 2 NP Completeness 0 Garey and Johnson Computers and Intractability 1979 Descriptive Complexity 0 Immerman Descriptive Complexity 1999 3 Syllabus will be up soon on the course web site 0 httpwwwcs umass edu barring08601 There is a pointer there to the Spring 2002 web site and the syllabus there will be close to what we do here Rough guide 0 Formal Languages and Computability 9 lectures 0 Propositional and FirstOrder Logic 7 lectures 0 Complexity Theory 11 lectures CMPSCI 601 Review Of Regular Sets Lecturel 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 De nition The set of regular expressions 122 over alphabet E is the smallest set of strings such that l ifa E Ethena E RE 2 e E RE 3 I E RE 4 if e f 6 122 then so are the following a 8 U f b 8 0 f C 6 Examples 0 81 0 E R01 0 82 a U 7 o a U b E Ra 7 0 83 ababa E Ra b 0 Meanings 0 60000304 0i 1 iEN O an2 w 6 ab E 0m0d2 39 ababa w 6 MW 1 120111 E 0m0d2 Recall the meaning of Kleene star for any set A A E ii Ai i0 2 AouAluAguo E eUAUay 3yEAU E 1332n nEN1nEA Meaning of a Regular Expression 1 ifa E 2 then a 6 122 3a a 2 e E RE 6 e 3 7 E RE EUD 7 4 ife f 6 122 then so are e U f e o f 8 178 U f 178 U EU 178 O f 81709 W 1 u E 8771 E Em 175 8 De nition 11 A C 2 is regular iff 38 E REA 8 In other words a set A is regular iff there exists a regular expression that denotes it 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 C Q is the set of nal or accept states D1 S7q7a7b7617878 61 ltltS7agt78gt7ltlt87bgt7Qgt7ltltQ7agt7Qgt7ltltQ7bgt78gt 9 Cl a V 1 D1 w 6 ab 110112 E 0m0d2 1 ababa 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 C Q is the set of nal or accept states MN w 1 SinF 505 2 powersetofS A1AQS 10 Nn QOw o 39 7Qn170717Amq7Qn1 An ltltQO7Ogt7QOgt7 ltltQO71gt7QO791gt739 39 39 7 ltltQn71gt7Qn1gt You will Show in HW 1 that to accept Nn a DFA would need 2quot1 states 11 Proposition 12 Every NFA N can be translated into an NFA w0 etransitl39ons N39 SJ N N39 Proof GivenN QEAQOF16 ENQ727AI7907FI where A39qar38tq gt81gtt gtr F39 q 1 386396 38 12 Notation For a DFA D Q E 6 s F let 6q 11 be the state that D will be in after reading string 21 when started in q V0176 E q 5 27 wa E 505 27 w a D E w 6sw E F For an NFA without 6 transitions N Q 215 sF let Aq 11 be the set of states that N can be in after reading string 11 when started in q NUM 9 AV wa 2 U Ana 2 gt WM lt gt N E w Asw F7E 13 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 we 2 6 90 F 6Sa U Ara TEES F395 Q1SOF7 14 Claim For all 71 E 2 5 m7 w NMoW By induction on 17111203 5QO 10 AVG076 1w k1 wzua Inductively 6QO7 u N020 u WHQoLW 55qo7u7 a U AUquot a r 5q0u U A 7quot a TEAq0u Aq ua Therefore D N 15 Theorem 14 Kleene s Th Let A C 2 be any lan guage Then the following are equivalent 1 A Df0r some DFA D 2 A Nf0r some NFA N WO 6 transitions 3 A Nf0r some NFA N 4 A e for some regular expression e 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 e that there is an NFA N with e N e 80 e gt 16 II to Union C oncatenation LNLN1LN2 LNLN1LN2 N1 Kleene Star LltNgt ltLltN1gt N 17 3e4LaNz rwnLEA ij ww E w j E A22w n0 intermediate state 7 gt k L9 a1jEAiQ U 517Zj 1 k1 k k k k L Lij U Lik1Lk1k1 Lk1j k L kI kI 18

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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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