Class Note for C SC 473 at UA
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 Arizona taught by a professor in Fall. Since its upload, it has received 16 views.
Reviews for Class Note for C SC 473 at UA
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
CSC 473 Automata Grammars amp Languages Theory of Computation Lecture 02 Preliminaries c sc m Amman cmm e Languages 8222007 Sets mathematics and logic can be constructed One small hierarchy of concepts in this course derives gtG Grammar G V Z R S mg seederee lunction reiatton tnteger tuple set C so we Autumn39s awe Laws Set primitive notion of aggregatequot from which all of rational Sets cont d or false when x is replaced by a particular object PJcxis odd Main predteete ter setwmembership 1 5A Some axioms of set theory AE 1ff VXXEAltXEE L 7 w E 2 w ends in letter 23 Fn 7 n AygtOZgt y C so we Autumn39s awe Laws Predicate Px a statement about a variable x that is true Axtom et Extension 3 set is determined by its extension Axtom et SQecilicalion For every setAand predteete PJc there is eeettx s A 1 Px olallelementsolAlorwhichPistrue EX K 2 x is positive and not prime 46831012 3 X X 15 a string over 3 ab 2 3 A 3x S39Eiy 32 x gt 0 O A x z Lecture 02 CSC 473 Automata Grammars amp Languages Sets cont d Operations and relations on sets A g B subset A c B proper subset A u E union A m B intersection g complement A r B dmerence A Size oi set Special sets empty set W to 1 natural numbers z t 7 271 0 1 2 integers Sets of sets Powerset A x X g A 2 C so on Autumn39s Gamma Laws 8222007 shoot your ambassador S R S RgtS T pay T shot T Fpay Fshot T Fpay T shot T Tpay Fshot F C so on Autumn39s Gamma Laws Logical Implication Material implication R gt S lfyou do not pay us 1 M by midnight R we will Logical Implication cont d shoot your ambassador Q P Q PaQ Tpay Tshot T Fpay Fshot T Fpay Tshot T T pay F shot F C so on Autumn39s Gamma Laws P gt Q If you pay us 1 M by midnight P we will not Lecture 02 CSC 473 Automata Grammars amp Languages 8222007 Quantifiers V Vx for all X 3 3x there exists X Ex defining big Ohquot relationship between functions x 0x2 a SC gt 0 EN gt 0 Vx 2 N fx C x2 Ex continuity of a function at a point epsilondelta defnquot x continuous at C t Vs gt O 35 gt O Vx ix 7 cl lt 5 2 lfx 7 Hal lt s Abe Lincoln39s quote canfoolpt can fool petson p at time t VP at Canfoolp t ABP Vt Canfoolp t A Vp Vt Canfoolp t C so on Autumn Gamma Laws Quantifiers cont d Relationship between V and 3 av 2 3 Ex cannot fool all of the people all of the timequot VP Vt Canfoolpt E 3p 3t canfoolpt Ex noncontinuity at a point Vs gt 165 gt O Vx ix 7 cl lt 5 2 l x r fcl lt s E as gt 0 V5 gt 0 3x ix 7 cl lt 5 A l x r fcl 2 s C so on Autumn Gamma Laws Sets amp Predicates U universe Sets Logical Predicates Px Pom Poo AmB mmBa AuB AJcvBx AB AxVaBx Pz 39 3101300 PU 7 39 VxPx U P P poo xeP Pxtme Pg VxPxQx Po VxPxltQx C so on Amman Gmdbhws 9 Lecture 02 3 CSC 473 Automata Grammars amp Languages 8222007 Tuples 37 unordered pair 2tuple 37 ordered pair 37 E 373 73 2 377 Generalize to ntuple atY a2 a3 an Defn Cartesian Product AXBEab IaEAAbEB Generalization A xAzx x A C so on Autumn39s Gamma Languages Binary Relations Defn a binary relation R from A to B is a subset of A XB R g A X B domain R a e A 3 e B a b e R range R be B Jae Aab R Defn a functionf fromA to B written fA a8 is a relationf gAXB thatis singlevalued ie Vabcab e f ac e f 5 b c Defn onetoone injection onto surjection onetoone correspondence bijection See Delinition 412 p 175 text Also see below C so on Autumn39s Gamma Languages Binary Relations 3 views R g A X B E relation predicate mm W preux m e R m R lb 310 e lt 3 lt 10 lt 310 Ch avleAndvew e Charles ithlthemfAndvew isF thWf ixFatherof Charles Ammw C so on Autumn39s Gamma Languages Lecture 02 4 CSC 473 Automata Grammars amp Languages Ex division with remainder E MMWW ExcircleC g x C X y X2 y Ex Relational Database R Time X Faculty X Room IZUR Time X Room Grammar derives relation E 5 N E 5 E N E 5 E N C so on Nam Gamma Laws Why Relations Generalize Functions Ex functions y X2 lssquareo xl y lssquareof l 0 0 l l 2 4 I 3 9 I EnmqrltgtnmqrA0 rltm Elll0l20l ASE12 i Q l 8222007 Relational Calculus RgAxB 71 R baabER If RAx5saxc then ROSaC3bEBabERAbc C so on Nam Gamma Laws es Relational Inverse RgAxB 39 RIQBXA lt gt Q 2 mef Chzldof Dzvzvaf MulrzpleOf Hzt 1mm i R i R i A B a A C so on Nam Gamma Laws Lecture 02 CSC 473 Automata Grammars amp Languages 8222007 The Calculus IAaaa A 3 Proposition If RAXBSBXCTCgtltD RoSoTRoSoT 7 R o 5quot s o Rquot Rafi R ROIEIA0RR RUSquot Rquotusquot RUSoTRoTUSoT Ro oR c 5cm Aime Gammath 5 Proving a Proposition about Relations Thm R o Squot squot o Rquot Pf a R o squot g squot o Rquot Let Ca R o S Then aC E R o S and 3b 6 B ab e R A bc e S bydefinition of So ma Rquot and ab 6 Squot i a Re and so ca S39 arbitrarilyR 5 Q S b Squot o Rquot g R o Squot Let c a g Squot e RquotThen3b e B b e squot and ba e R39je So bc e S A b e R implying ac e R o 5 Hence a a g R o Squot Since 011 was chosen arbitrarily b follows Slince c a was chosen a R7 c a c 5cm Aime Gammath 7 Relational Properties R gAxB Relational calculus Qredicate calculus name R o R71 Q IA VaElbaRb total dam R A R71 o R IE VabcaRb A aRC singler gt bc valued R e Rquot IA VacbaRb A cRb 171 gt ac injection R71 o R Q IE VbElaaRb onto surjection range R B Pfl Va 6 Ata a E R o R39 ltgt VaaR o R a ltgt Va baRb A bR Ja ltgt Va baRb Pf2 Vbb iaiRquot o Rb gt b b ltgt Vbb VabRquota A aRb gt b b ltgt Vbb WaeRb A aRb gt b b Pf 3 like 2 Pf4 like 1 c 5cm Aime Gammath 5 Lecture 02 6 CSC 473 Automata Grammars amp Languages Family Relationships P XPy E X is Parent of y P 1 isChildol P o P a PP a P2 Grandparent P2Pquot n 2 0 Greatquot Grandparent P lP Sibling Sibling orsef P39lP m f Sibling 71 PP Seller asexualreproductiononly C so on We Gamma Laws PZP 1 Parent Parent 01 child With olispringl 8222007 Family Relationships cont d i P ZP Nephew mece orchild P ij l P 1P2 Uncle Auntor PP 2 Childw oilspring 39 P4192 idoousm Once Removed or P U P2 ParentorGrandparent P U P2 U P3 U Ancestor C so on We Gamma Laws Pingrl P 2P3 lS CouSannce Removed or P E P U P2 U P3 U TransmveclosureolP 2o Binary Relations on A to itself A RgAxA sgAxA RUS ROS AgtltA7R Exny yx1R7lgtlt7V R R lt R3lt R RUR UR3Ur l R R UIlt Thm R R U I C so on We Gamma Laws Lecture 02 CSC 473 Automata Grammars amp Languages 8222007 Properties of R g A X A Name Deln Flelagional Calculus Rrellexive Va 3123 R 3 IA Rsymmetric Vab aRb gt bRa R R l Rtransitive Vabc aRb bRC gtaRC RoRgR R an equivalence relleXive symmetric amp transitive relation c 5cm Nam swabMs 22 A False Proof About Relations Theorem Clearly any symmetric and transitive relation R must be reflexive Pf Assume thatR is symmetric and transitive Then Va b aRb gt bRa By transitivity a Rb bRa gt aRa Since a was chosen arbitrarily it follows that V a aRa D What39swrong sym amp 7 R 9 sym ll main m is true meme argument is correcll c 5cm Nam swabMs 23 RgAxA Digraphs 0 1 Matrices A a b C d Riabbab0cdl a b C d a 0 l 0 0 b l 0 l 0 MR c 0 0 0 l d 0 0 0 0 GR b c d C so on Amman Gmdbhws 2 Lecture 02 8 CSC 473 Automata Grammars amp Languages 8222007 Relations Digraphs Matrices cont d R2aIaaCbbbdl a b C d OOl O OOOH OOl O 0 l 0 l 0 l 0 0 0 0 0 0 OOOH C so on Autumn39s aims Laws Relations Digraphs Matrices cont d R3 labadbab0l 0 1 0 1 3 1 o 1 o 3 Ma MO 0 0 0 0 0 0 0 0 GR3 C so on Autumn39s aims Laws Relations Digraphs Matrices cont d R taaacbbbdi l 0 l 0 0 l 0 1 MR4 MR MR2H 0 0 0 0 l 0 0 0 0 60 Repeats C so on Autumn39s aims Laws Lecture 02 9 CSC 473 Automata Grammars amp Languages RRoR2oR3oR4 l l 0 0 OOHH OOHH OHHH c SC on Autumn swat Laws Relations Digraphs Matrices cont d 8222007 Transitive Closure finite graph c SC on Autumn swat Laws Transitive Closure a Reachability Defn a reachesb in relation digraph R iff 3kgt03aua1 ahauaakb V1O s 1 s k 7 121Ranj Prop a reachesb in Riff aRtb Then RRURQU quotURquot Ex may need to go up to Rquot c SC on Autumn swat Laws Thm LetR A x Abearelation where l A l H Pf Longest possible path in GR that will not repeat an edge is of length n This path will result in an edge in Rquot R R20 O C R3 30 Lecture 02 10 CSC 473 Automata Grammars amp Languages 8222007 Strings and Languages In this course a language is simply a set ofsm39ngsa programming languagequot is much more complex alphabetZ a finite set of symbols String word over 2 M sequence of symbols e the empty or null string 8 i e le length of string w What is a string preclsely7 Stnng w ot length n is a lunction w ln gt Z wj jth symbol String ops X I y Xy concaenaion Xyz XWZ Xs 8X X powers 0 7 11 7 1 w 7 S w 7 w w C so as Autumn smut Laws Strings and Languages cont d 2 w w is a suing over 2 e e 2 Language L over 2 a subsetL 2 Ex 2 la bl L0 25 L1 2 L2 la n prime L3 laa ab ba bbl L4 nab n e W Ex 2ASCcodes Lt blank040 e2 Qii liiu C so as Autumn smut Laws Strings and Languages cont d Language ops Set operatogs 2 L2 g 1 A LtUIutLtoLuLtaIutfmt 7L Concatenation Ll39L2X39yZXELYEL2 Powers L0 S Li L1 39 L EX 2 ab L1 aab L2 bc c L L abcacabbc ExL 22 In E W LL1 lays L3 a U Lglal U Lglsl azn znewlULZlaliiEWl C so as Autumn smut Laws Lecture 02 11 CSC 473 Automata Grammars amp Languages 8222007 Strings and Languages cont d Language ops cont d Dem Kreene erasurersrar Lw3k20 w wlwz wk 3wmWk E L Nore s E L Dem L LL Ex s Ex 2 a b EWaE w w e 2 has at least one a bmebf w w e 2 has exactly one a XYaEWa c SC on Autumn39s Gamma Laws Strings and Languages cont d Theorem E L0 U L1 U L2 U U L1 Pfw e L ltgt 3k 2 03w e L10 Hwk E L w w w lt 3k 2 Ex 2 aim HbHaW s u rbHaf u bua bnaf u b a b a b ref u s u wa Ob Ubw lb Ubw 21 u wa 31 u sUbw0bvlbv2bv3bvm s u b a b c SC on Autumn39s Gamma Laws Strings and Languages cont d ExL a2a3 L s u a2 af Ex Ha bff a by Ex L u a L c SC on Autumn39s Gamma Laws Lecture 02 12 CSC 473 Automata Grammars amp Languages 8222007 Methods of Proof Construction exhibit the object guaranteed by the theorem Ex Construction of a regular expression given a FA Contradiction To show IP Assume P and derive a contraction or clear falsity reduction ad absurdum Ex our proof of undecidability of the halting problem Induction to prove Pn holds for all nonnegative integers n PO base basis Vk Pk e Pk 1 step Vn Pn conclusion lnduc on VD Pn C SC 473 Automata Grammars amp Languages A Rule of Inference PO base Vk Pk a Pk 1 step VD Pn conclusion Prove Pk aPk1 ohalts Vn a1gorithm gt W Pn C SC 473 Automata Grammars amp Languages Lecture 02 13 CSC 473 Automata Grammars amp Languages Kinds of Induction Simple induction Equivalent 1 Pk e 1 gt Pk 1v Ptn CourseofValues Induction PO PM V11 Pm C so on Autumn39s Gamma Laws 8222007 EX Balanced Parentheses are defined inductively by The empty string e is balanced lwls balanced soiww H w kare balanced so is w Nothing else is balanced except by the above rules Remark a grammar for balanced strings is B 4 S B 4 B B 4 BB Exam pl es Baianced 39Unbalamed C so on Autumn39s Gamma Laws Defn The strings having balanced parentheses over Parentheses cont d Ca twisiwhand Cb ny wXy Hixl ZleJ prove 2 directions C so on Autumn39s Gamma Laws Thm A string w is balanced iff it has the prefix property Comment thtsttt cat alogical equivalenceJmeanswe have to l a stnrg is balanced ll hasthe pielix pmpem2 Lemma t below l a stnrg has the pielix ptopetty then ll is balanced e Lemma 2 Defn C A string w over has the prefixproperty C iff Note the prefix property can be checked in a LR scan of the string using a counter this is what calculators do Lecture 02 14 CSC 473 Automata Grammars amp Languages Parentheses contquotd 8222007 c 5cm Autumn swabMs 3 Parentheses cont d Thm A word w is balanced iff it has the prefix property Lemma 1 w balanced 2 w has prefix property C Pf Induction on le Basew0 2 ws gtw satisfies C Step Let lwln Assume IH all strings shorter than n that are balanced satisfy C Let w be balanced Two cases are possible Case wuv where uv are balanced By lH u v satisfy C Then lwlaullvldullvl wl and so w satisfies Ca Next consider a prefix s 0fwuv If s is a prefix of u then because i s l 2 l s l by lH then w satisfies Cb for this prefix c sconAmnmu swabMs Parentheses cont d lfsutwheretisaprefixofvthen l t l 2i t l bylHandso lSllLIlltlli 1lltl ZlUlltllSl and so w satisfies Cb in this case Case w u where u is balanced By IH 4 satisfies C and so clearly so does 14 c 5cm Autumn swabMs 5 Lecture 02 15 CSC 473 Automata Grammars amp Languages C so on Autumn39s aims Laws Parentheses cont d Lemma 2 w satisfies C 2 w is balanced Pf Induction on le Base ws is balanced by definition Step Let lwln gt0 Assume IH all strings shorter than n that satis C are balanced Let w have prefix property C Letx be the shortest prefix of w such thatl X l l X l Such a prefix exits since w has this property Casexw Then w u where 4 satisfies C By lH u is balanced and so then so is w Case xvw with we Nowx satisfies Ca by assumption and satisfies Cb since w does So by lH x is balanced 8222007 C so on Autumn39s aims Laws Parentheses cont d We claim thatvhas propertyC Since l X ll X l andl w ll w l then l V ll V l and so v satisfies Ca Suppose there were a prefix y of v suchthatl y lltl y l Then l XY lltl XY l Which would violate the prefix property of w Thus it must bethatl y l2l y l SovsatisliesCb By lH v is balanced Since both 1 and v are balanced wxv is balanced Lecture 02 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'