Class Note for CMPSCI 601 at UMass(20)
Class Note for CMPSCI 601 at UMass(20)
Popular in Course
Popular in Department
This 23 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 10 views.
Reviews for Class Note for CMPSCI 601 at UMass(20)
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 5 De nition A contextfree grammar CFG is a 4 tuple G V Z R S 0 V variables nonterrninals 0 Z terminals 0 R rules productions R g V X V U EV S e V 0 V Z R are all nite Pumping Lemma for Regular Sets Let D QZ6 101 be a DFA Let n Let w 6 131 st 2 n Then 3xyz E 23 st the following all hold 0 gt 0 and 0 Vk 2 maxi92 6 131 CFL Pumping Lemma Let A be a CFL Then there is a constant 72 depending only on A such that if z E A and 121 2 n then there exist strings u v w as y such that 0 z uvwacy and 0 1223 2 1 and 0 122wa g n and 0 for all k E N Maliwacky E A Prop P anbmanbm 1 n m E N is not a CFL Prop NONC FL anbncn n E N is not a CFL 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 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 CMPSCI 601 Pushdown Automata PDA S Lecture 5 De nition A pushdown automaton PDA is a 7 tuple P Q E l A go 20 F 0 Q nite set of states 0 Z 2 input alphabet 0 l stack alphabet 0 A g Q X 23 X l X Q X l nite set of transitions 0 go 63 Q start state 0 20 E l initial stack symbol 0 F g Q nal states PDA NFA stack Z 1062 l QOaZOgtq7X7q F7X F Theorem 51 Let A g 23 be any language Then the following are equivalent 1 A G f0r 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 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 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 We have all rules of the form Am gt Apr1n and a rule Am gt afler Whenever moves of the PDA warrant it Q CMPSCI 601 Boolean Logic Syntax Lecture 5 Boolean variables X 321322323 A boolean variable represents an atomic statement that may be either true or false There may be in nitely many of these available Boolean expressions 0 atomic 92 T top l bottom 3904V18L 067 Oz 04 gt 18 06 lt gt 7 for 0418 Boolean expressions Note that any particular expression is a nite string and thus may use only nitely many variables A literal is an atomic expression or its negation xi earl T i As you may know the choice of operators is somewhat arbitary as long as we have a complete set one that suf ces to simulate all boolean functions On HWl we argued that A V e is already a complete set The expressions form a contextfree language As we mentioned before we may cheat by omitting paren theses etc as long as the parsing is clear Even with the cheating it s not too hard to tell Whether a string is a valid expression Examples of boolean expressions 0 331 0 2 V 112 0 131 gt 132 0a gtbb gtc gta gtc CMPSCI 601 Boolean Logic Semantics Lecture 5 A boolean expression has a meaning a truth value of true or false once we know the truth values of all the individual variables A truth assignment is a function T X g X gt true false where X is the set of all variables An as signment is appropriate to an expression 0 if it assigns a value to all variables used in p The doubletumstile symbol read as models de notes the relationship between a truth assignment and an expression The statement T go read as T models cp simply says 0 is true under T If T is appropriate to p we de ne when T p is true by induction on the structure of 0 T is true and l is false for any T A variable xi is true iff T says that it is Ifcpz oz T piffb0thT aandT 8 IfltpOH8TlchiffeitherTl2a0rle or both 39Ifltpa gt8TltpunlessTozandT 8 Ifcpz ozlt gt8T ltpiffT aandT 8are both true or both false 10 De nition 52 oz and 8 are semantically equivalent 04 E 3 iff for all T appropriate to a and 8 T l 04 lt gt 3 Examples 331 E 1VL a gta E T 0a gtb E b gt a a gtb E aVb ab E av b ab E aA b aVb E bVa aVbc E abC taVbc E aVbac a E lla ll Proposition 53 Every boolean expression up is equiva lent to one in Conjunctive Normal Form CNF and to one in Disjunctl ve Normal Form DNF Proof DNF look at the truth table for p HHHHOOOOR HHOOHHOOCQ z lt gt y 0 1 O 1 1 1 O O 1 1 O O O O 1 1 O O O 1 O 1 1 1 Q syAz Q syAZ acyAZ acyAz CNF put ap in DNF Use De Morgan s law olvvok 2 e1 ak 12 De nition 54 A boolean expression 0 is satis able iff there exists T f p p is valid iff for all T appropriate to p T p Q Proposition 55 For any boolecm expression p p E UNSAT 42gt ap 6 VALID UNSAT g VALID VALID g UNSAT Proposition 56 0 p is unsatis able i cp E i p is satis able i cp E i a pisvalidi cp E T 13 CMPSCI 601 Relations With Other Models Lecture 5 A boolean expression speci es a boolean function of its variables It s natural to ask how the computation of this function ts into our other models of computation A boolean expression of length 3 can be converted into an SLP of length 86 by induction on the de nition of the expression If we already have SLP s computing 0 and 8 we can concatenate them and then with 01 more instructions compute any of the expressions oz 8 04 V 8 04 gt 8 or 04 lt gt 8 l4 Given any SLP and any of its instructions the output of the instruction is a boolean expression and thus there is some boolean expression that computes it Can we be sure that a short SLP leads to a short expression We can if the SLP is readonce meaning that each noninput variable occurs only once on the righthand side of an in struction You ll prove on HW2 that the value of 3 th in struction of a readonce SLP has an expression of length 06 It is unknown whether every polynomialsize SLP can be made readonce while keeping the size polynomial As we may prove later in the course this is equivalent to the question of whether every polynomialsize SLP can be given depth Olog n while keeping its size polynomial It is generally conjectured that it cannot 15 What about the rstorder model and boolean expres sions We can convert a V or El quanti er into a boolean ex pression using or V For example Va ltpa can be equivalently written ltpOltplltpn l where each of the ltpz39 s is one of the input bits By induction we can prove that a rstorder formula of quanti er depth d corresponds to a boolean expression in the atomic variables of length 002d Try this In this case it is known that there are polynomiallength boolean expressions that cannot be converted into rst order formulas so that the boolean expresssions are strictly more powerful We won t get to the proof of this due to Mike Sipser and three others in 1981 in this course 16 We have de ned several properties of boolean expres sions validity satis ability and their negations It is natural to ask now dif cult it is for an algorithm to take an expression as input and determine whether it is valid or satis able The method of truth tables gives us a way to answer these problems though not a very satisfactory one Given a formula in n variables there are 2 different settings of the variables 2 rows of the truth table We know how to evaluate the formula in each of these settings and thus given enough time we know how to create the entire truth table and see whether there is at least one true row or at least one false row Of course except for very small n this running time is prohibitively large Is there a better way to answer the questions We don t know and we will see that this pos sibility is tied to the major open questions of complexity theory One thing we do know is that in some circumstances we can determine the validity or satis ability of an expres sion without computing its entire truth table by giving a formal proof in some system This is our next topic 17 CMPSCI 601 The Fitch Proof System Lecture 5 If two expressions are equivalent or if one is a tautologi cal consequence of the other this fact can be established by truth tables But the 2 18 lines of the truth table are far too many to work with unless k is small We need a more ef cient method to establish tautologies BE provides a proof system called Fitch or 75 At this point in the course we are concerned with the proposi tional subset 1 of Fitch leaving out rules dealing with quanti ers 18 A Fitch proof is a sequence of expressions each one of which is justi ed in terms of previous ones There are twelve proof rules that tell us when a statement is justi ed Fitch has no axioms statements assumed to be true with out proof but we typically start with some premises and reach a conclusion that follows from those premises If from a set P of premises we can derive p we write P l ap read as P proves 90 This single turnstile symbol l is not to be confused with the double turnstile symbol l9 CMPSCI 601 7378 Propositional Proof Rules Lecture 5 These are conveniently listed on pages 5579 of BE Intro From P1 Pm derive P1 Pn Elim From P1 Pm derive a Intro From B derive P1 Pn Elim From P1 Pm if you have derived 539 sep arately from each Pi derive S e Intro If you have derived l from P derive P Elim From P derive P l Intro From P and P derive l l Elim From l derive P any P gt Intro If you have derived Q from P derive P gt Q gt Elim From P gt Q and P derive Q also called modus ponens lt gt Intro If you have derived Q from P and have derived P from Q derive P lt gt Q lt gt Elim From P lt gt Q and P derive Q 20 As you practice with the Fitch software there are two things you learn how to do You must learn when a move is legal and then when a move is a good idea In chess we call a player a beginner once they know all the moves but after a lifetime of play they will still have more to learn about how to play well The rst natural computational problem that Fitch creates is determining whether a proof is valid The software does this for your proofs and you learn to do it mentally as you look for proofs 21 A proof is valid if each step is valid and a step is valid if it follows from previous steps by a rule Eight of the rules require certain other statements to be available meaning that they are active premises or have been proved within the current scope But four of the rules Elim A In tro gt Intro and lt gt Intro require not previous state ments but previous proofs This means that Fitch proofs have a nested structure with derivations nested within other derivations We can de ne the available statements at any given point in the proof as those that are in the current derivation or any of the derivations containing the current one As computer scientists we naturally think of a stack to maintain the nesting structure At any given time we are engaged in a derivation that has certain active premises Since premises are inherited by subderivations we can keep them in a stack 22 Testing validity of a step thus involves a single pass over the current premise stack and the current derivation to see whether all the required statements or derivations for the step are there This doesn t look to be a very dif cult task We haven t yet formalized the notion of polynomial time yet in this course but once we do we can see that check ing a Fitch proof for validity takes polynomial time in the length of the proof What about the second problem of nding a reasonably short valid proof when one exists This is more dif cult of course falling into the category of arti cial in telligence There are useful heuristics but no reliable general method We ll show in the next lecture that every valid statement has a proof in Fitch But even this completeness theo rem won t tell us whether a short ie polynomiallength proof exists for every tautology This latter question is open as we ll see 23
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'