Class Note for C SC 473 with Professor Downey at UA
Class Note for C SC 473 with Professor Downey at UA
Popular in Course
Popular in Department
This 32 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 19 views.
Reviews for Class Note for C SC 473 with Professor Downey 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 9222007 Theory of Computation Lecture 03 Finite Automata c sc m Amman 01mm a Language Finite Automata Switching Theory UQB Booiean operatorsGatesEiem Switching Ops x y xAy xvy My 1 o o o o o 1 o 1 o 1 1 1 o o 1 1 o 1 1 1 1 o C so on Autumn39s Gamma Laws Boolean Functions Combinatorial Circuits Circuit x 9 x2 X 2 sum 19 H H x1 x2 x3 22 new carry X x A x2 01a carry F full adder c 5cm Aim Qmaws 3 Lecture 03 1 CSC 473 Automata Grammars amp Languages 9222007 Boolean Functions Comb Circuits cont d Table representing F c sconAmnmu swabMs Boolean Functions Comb Circuits cont d Equations representing F 912 Xl DXZ X3 Zl 22 922 X1 9 X2 X3 V Xl X2 General scheme n inputs m outputs er er 7 Zn 9Xlr X2 r X 91Xlr X2 r X r r gmXlr X2 r Xn c sconAmnmu swabMs 5 Finite Automata Sequential Circuits Add memory39 elements delay elements yltigt D ylti 1 combinatorial circuit x 39f gtE 5139 f 34139 r 34139 l r 34139 2 r Finiteofdeay elements possible 2 3 d 31 f ii I Xi l r i 01 c sconAmnmu swabMs 5 Lecture 03 CSC 473 Automata Grammars amp Languages Finite Automata Sequential Circuits Ex sequential adder add 2 binary numbers low order bits received first 10014 X10 mhx 0 a sequential net circuit 1110 xju full X2 adder Z1 mm 1 Ytu ylu c SC on tam Gamma Laws 9222007 Finite Automata Sequential Circuits b NextState amp Output Equations ytti 1 Dad 6 xzti A yi v xlti A xzu 21139 xi e x2i e yi 0 Transition Table state space to 1 qn cm 1nput alphabet El 00 01 10 11 Output alphabet FO 1 next statejoutput table X 00 01 10 11 1 go In0 In1 CIt16L 7 q In1 L 7 q10q1 a mum emanates Finite Automata Sequential Circuits d State Diagram omO 010 c SC on tam Gamma Laws Lecture 03 CSC 473 Automata Grammars amp Languages 9222007 A Finite Automata Sequential Circuits e FiniteState Transducer Mealy Machine Asempie M Q 2 F 6 go where Q go r 411 me setoistates go startstate 2 i 00 01 10 11 imputaipnabet F 0 l outputaiphabet 5 Q x 2 gt Q X F transitionoutputiunction 5qor 00 qor 0 Why 01 qor 1 5qor 10 qor 1 5qor 11 q 0 g 01 q 0 eta c SC on We awe Laws General Sequential Network B lt0 1 or x 21 boolean 5 B39I S function X mos Z A B state space B y i yS Ki 5071 7 41 5qr a c SC on We awe Laws Three Types of Automata a1 6 2 ama3aa1 cmccc n 2 n 3 2 1 M t me transducer an 833231 M gtYesi gt No0 recognizer acceptor M Enumerator generator c SC on We awe Laws Lecture 03 4 Slide 10 p1 Mealy FST is called quottransition outputquot since outputs are associated with state transitions Moore FST is called quotstate outputquot since outputs are associated with entry to target state of a transition Peter J Downey 862007 CSC 473 Automata Grammars amp Languages 9222007 Machines that Recognize Detection of an event Le a pattern in input Recggnition of just those words in some language L Definition of a language Ex detect abab a nonoverlapping occurrences C so on Autumn awe Laws EXCComments Filter in thelexical scanner a e at g empty a transducer notatlon 15 m out C so on Autumn awe Laws Finite Automaton Finite State Machine FSA Defn 15 A deterministic nite automaton is a 5tuple M Q 2 6 qt F Q is a tinite set the states 2 is a itnite set the aphabet 5 q Q x 2 gt Q isthe transiton function E Q isthe startstate Q isthe setotaeeeptingttinai states Ex M0 to 2 561 F Q ltth q Q2 arb F qt We a q 5qo b q2 5q a q2 5amp1 b qt 5q2 a q2 5q2 13 M i i i Q C so on Autumn awe Laws Lecture 03 5 CSC 473 Automata Grammars amp Languages 9222007 How FA Compute FA M Q 2 3 gal F is a finite structurklike a program xed and static Need to define the behavior of Mon inputw Sequence of configurations Like trace of a program on given data Dynamic and inputrdependent Ex start Mo on input W ababa Look at sequence of moves determined by the transition function qo ababa I qj babe qu aba r q ba Hqg a Hq 8 qo ababa 1 q 5 Since in accepting state when input exhausted w is recognized by M0 c 5cm Atom swam 5 How FA Compute cont d Given a FA M Q 2 3 9390 F Defn con guration ofM is an elementof Q X 2 Defn yields in one step or moves relation I between configurations is defined by q aw Hq w gt 5q a q whereae Zw e Z qq e Q Notes isaiunction since is q 8 r is undefined Defn yields is the relation i1 Means moves it zero or more steps toquot q w I CL w Defn A string w is recognized accepted byM cgt 3 f e F qt w Hf s c 5cm Atom swam 7 How FA Compute cont d Defn The language recognized accepted by M is LM w M accepts w w 3f 6 F qr w Hf 8 Defn 116 A language Sis regulariff there is some FA thatrecognizesitie3M M is 3 FA A s LM Exn FA M0 go a r qua qr aha Hg 8 go abiia 393 q 8 39 HMO ab a 1 Z 0 c 5cm Atom swam 5 Lecture 03 CSC 473 Automata Grammars amp Languages 9222007 Example eke change forzr30 ampvend coiiee Coin checker for 30 coffee 2ndq c 5cm Autumn39s swabMs 9 Regular Operations amp Regular Expressions The regular operations on languages are union o concatenation arid Kieene star So called because the class of regular languages are closedunder them ie applying these operators to regular languages results in a regular language We will prove these closure results later In fact these three operations o actually characterize what it means to be a regular language any regular language can be built up from alphabet symbols and a finite number of these regular operations This motivates the notion of regular expression a sequence of symbols like an arithmetic expression that defines a regular language using regular ops c 5cm Autumn39s swabMs 2 Regular Expressions A syntax for describing sets of strings languages Terse Eiiminatesfussy lquot Reminisceniofariihmeiic expressions Obeys some useful quotalgebraquot e g E F J EF Syntax for regular expressions over 2 E gt EE text uses u not some authors use i gt EE usually suppress the in E E gt E gt 9 some authors use A gt Q gta for eachainZ suppress where possible ab a not a b a c scouAmnmu Gammath 2 Lecture 03 7 CSC 473 Automata Grammars amp Languages 9222007 Regular Expressions cont d Meaning rules for the syntax The meaning denotation of an expression LE is a set of strings a language Rules exgression E language L E Q Q l a a 8 l8 EF LEULF EF LELF E LE c SCOBAmmuu cameraMs 22 Reg Expr Examples Equivalence aba L a bl la ab llal lbl l ab a M abaabaab w e 2 z w has 2 2 3395 bababab w s 2 z 3 divides a39s PASCAL unsigned numbers d019 dd5ddsEi sdd w s 2 aZab 2bab w e 2 z w begins amp ends same Defn EF ltgtLE LF e E F EF EooEo EFGEFG EFGEFEG EeeEE c 5cm Adam swam 23 Nondeterminism Real computing devices are determinis c the current configuration and instruction determines the next configuration The i relation is a function Why the concept of nondeterminism provides poweildl economical descrlpllve ablllly provides away to speclly languages Wiinodi oveieoecilying and complex nandling ol cases Carl be algoninmlcallyconvened to a determll llsllc descrlpllol l at the sacrlllce ol some economy and Wiin added compleXlly Generallzatlol l ol determll llsm Ex abab occurs somewhere in w abab C so m We Gamma nieces Lecture 03 8 CSC 473 Automata Grammars amp Languages Nondeterminism cont d Exwz2ha522a s waa 9499 ab ab ab c SC on Nam swat Laws 9222007 s Moves Can Be Useful SNOBOL arithmetic constants no floating E c SC on Nam swat Laws Use to speciiy bpiionai charactersquotiike Unix command iine opt M 926 qoF a me set the states Q 2 a me set the aphaber qo E Q isihesrarrsrare F g Q iSihe seioiacaeprnanaU stares Ex M1 Q 2 5 qquot F Q goqr mm b qo 5qo b q arb 6 a q 5q1b q c SC on Nam swat Laws Nondeterministic Finite Automaton Defn 15 A deterministic nite automaton is a 5tuple 6 Q x 2 U 8 gt TQ transiton function 2ibi FZii 6qoaqg q b 1 M Lecture 03 CSC 473 Automata Grammars amp Languages 9222007 DFA VS NFA For eacn s a e q and mum symbo 2 Were ws exac y one cho ce 0 39 There may be mump e chowcestor new s a e or no nansmon s We same Wm Symbo denned a aH Eacn ransmon W b m d consumesuanmpmSymbo eremax eernoves a ono consume an npu charac er Spec a 39 0 NFA v Tnere can be cnans39 ov ermoves 39 E39mOVeS can crea e even more Gnome vor me negtlt npu charac er c SC on We Gamma Laws How NFA Compute Given aNFA M Q Zr 5r qe F Defn configuration qr W E Q X 2 Defn yieldsin onestep ormoves relation I between configurations q aw Hq w Q q 6 5q a q w Hq E7 Q q 6 5q 6 Snmove Defnyields I Means COULDmove m zero or more s eps 0quot Defn wis recognized accepted byMcgt 3 f e F qo w Hf s Same as betore bu has me meamng quotn were est s some sequence 01 moves nom me man conng 0 some acceoung conngquot c SC on We Gamma Laws How NFA Compute cont d Defn The language recognized accepted by M is LM w M accepts w w 3f 6 F qg W p JS 8 Ex In NFA M1 go aabbba Ii go 8 Tns prowdes no quotewdencequot mm mm s accep ed or no Howeven a so we a separa efompmauon sequence go aabbba I ql 8 And so mm s recogrnzed c SC on We Gamma Laws Lecture 03 10 CSC 473 Automata Grammars amp Languages 9222007 Tree of Computations Ex NFAM qo aabbba go abbba l qor bbba qo bba q bba qo ba q ba l qo a q 3 qle F G 3 accepting null Computation W E X evidence qquot 8 weuMg C so on Amman amicth 3 Computation Tree Example EX L w wbegins amp ends same l ababa 1 abab l 2 baba 2 bath l 2 Elba 2 ab A 4quot 2 ba 3 ba 2 b 3 b t 2 a 2 g X 2 e 3 6 36F X c sconAmnmu swabMs 32 Example with s Moves String length a multiple of 2 or 3 0 322 2 322 4 aa 39 3 aa 5 aa 2 a 6 a 3 s 4 s X 45F Acceptaaa C so 073 Autumn Gmi hws 33 Lecture 03 11 CSC 473 Automata Grammars amp Languages Example with s Moves a b 0 2313 a S 1 a b 0 ab 39 39 XS 1 ab 0 b a X 1 b l 8 16F d Acceptaab games consume no input symbols c sc m Autumn39s ems Laws 9222007 Equivalence of NFA to DFA We Show basic idea assumin NFA has no ermoves Then modily the construction lor NFAS with ermoves final state is among those reached c sc m Autumn39s ems Laws There is an algorithm to convert any NFA into a DFA EX L x last symbol ofx appeared previously Zab Idea given input string keep track of all possible reached states after reading each letter At end of input see if a Computation paths through NFA No on w abba Equivalence of NFA and DFA cont d c sconAmnmu swam S e Lecture 03 12 CSC 473 Automata Grammars amp Languages 9222007 Equivalence of NFA and DFA cont d Idea keep a list of all possible states reachable by each prefix of w parallel worldsquot For NFA N0 a b b a lp a lp a lp a lp a lp q qr q q r r r S S ebba lp alp q r S abba E LNO since lpqrs H F i Q 37 C so on Autumn Gamma Laws Equivalence of NFA and DFA cont d Equivalent DFA Mwill have State set Q Alphabet Start state set 110 Accepting states X Q Xn F 1 Q Deterministic transition function 6 Q X gt Q Ex For NFA N0 5 13 q a 13 q S M p q b p q r 5 pl a Iaq 5 pl 13 Iar C so on Autumn Gamma Laws Equivalence of NFA and DFA cont d Thm RabinScott Construction Let L IAN for some NFA Nwith no emoves There is an algorithm to constuct a DFA M equivalent to N ie with LM IAN PfGiven N we construct a DFA M and then verify that it recognizes the same set as N Construction Given NFA N Q E 5 s F construct M er 2 5 S F where Q Qs isiF iXe Q an and 5 Q XZ gt Q is defined as VS Q a E 2 55 5 a q e Q 313 E Sq 5 50360 C so on Autumn Gamma Laws Lecture 03 CSC 473 Automata Grammars amp Languages Picture of 6 c SC on Autumn39s awe Laws Equivalence of NFA and DFA cont d 9222007 IQ I 2 9 SoMis a DFA 2 To show equivalence we prove the Lemma Pf By induction on the length of the input string w Base IwOQ Step Suppose IH the lemma is truve l c SC on Autumn39s awe Laws Equivalence of NFA and DFA cont d Verific ion Show 1 Mis a DFA and 2 LMLN 1 6 is a function by the construction and Q is finite p WH Mq 8 ltgt 3Qq e Q A Hp W I QAQ 8 pSIq8 lt2 p q lt2 Upb M L qb w llt Let i W l k lw ual V l kToshow p uanltq 8 e 3Qq e Q A Hp ua I iAQ s Then pu rs By IH 3Rr e R p u r 4R 8 By construction ofM q 6 MR a Let Using this with results in HQQ e Q A Hp ua r1202 a r lth 8 So HQQ e Q A Hp ua IZAQ s c SC on Autumn39s awe Laws Equivalence of NFA and DFA cont d 3 Assume p ua q 8 Then 3 state rwith p nah Mr a Nq 8 and q e 5r a Q 539R a Then 3Qq e Q R a 4Q s Lecture 03 14 CSC 473 Automata Grammars amp Languages 9222007 Equivalence of NFA and DFA cont d Assume 3Qq E Q Hp Ha I QAQ 8 Then 3 stateR with 5er a Q So lip Ha I QAR a I QAQ 8 1 By construction Eff R q e 5r a and r ai Nq 8 2 Since Hp u i 4R s we have from IH p u i gtr e 3 Combining 2 amp 3 So p ua C so on Autumn39s Gamma Laws Equivalence of NFA and DFA cont d We nowfinish the verification proof Let f e F From the Lemma 5 w f s ltgt 3Qf e Q 5 w I QAQ 8 a s VIM 14w s A Q n F Q Thatisy S Wl f forsome f e F ltgt s39 w FMQ s for some Q E F 39 MM LN El C so on Autumn39s Gamma Laws Example s Free NFA gt DFA Consider the previous NFA N0 Q 2 5 p s C so on Autumn39s Gamma Laws Lecture 03 15 CSC 473 Automata Grammars amp Languages Conversion NFA gt s free NFA erclosure 01 a state or set 01 states ER Belore picture For R g Q the eclosure ofR is C so on Autumn39s Gamma Laws EMU 1234136 78 E02 q e Q 3r e Rrsr q Ell 3 9222007 Conversion NFA gt s free NFA Coalesce all nodes reachable from 1 by emoves After picture a 12345673 b a E 1 1y 2 3y 4y 5y 6y 7y 8 C so on Autumn39s Gamma Laws Conversion NFA gt s free NFA equivalent NFA with no emoves Q Em q e Q F Eur f e F Pf Induction on the length of w D Verification From the Lemma S W f 8 lt2 ES W Ef 8 LN LN u C so on Autumn39s Gamma Laws Thm There is an algorithm to convert any NFA into an P Construction Given NFA N Q 2 5 S F constructnew NFA N QC 2 5 E is 1 F With Eq E 5 Epa ltgt 3p 6 Ep q E 513 a Lemmapr W Iq 8 ltgt Em r W I Eq r 8 Lecture 03 16 CSC 473 Automata Grammars amp Languages Conversion NFA gt DFA to convert any NFA into an equivalent DFA M Corollary 1 40 A language is regular cgt some NFA recognizes it Ex Start with an NFA N1 as follows c SC on Autumn Gamma Laws Thm 139 RabinScott Theorem There is an algorithm Pf Given NFA N convert it to an efree NFA NT Using the RabinScott construction convert N to an equivalent DFA 9222007 Conversion NFA gt DFA cont d Remove emoves c SC on Autumn Gamma Laws Regular Expression gt NFA Pf Induction on the of operator symbols in E Base E s Q aEZ with S operator symbols Let E have k1 ops Three cases and LE2 ZAMZ Construct the following NFA M c SC on Autumn Gamma Laws Thm 155 There is an algorithm that given a regular expression E constructs a NFA Nsuch that LE 14M OOr Step Assume lH the result is true of all expressions Case E E E2 By IH 3 FA M1M2 with ME LM1 Lecture 03 17 CSC 473 Automata Grammars amp Languages Case c SC on Nam Gamma Laws M2 FFUF2 9222007 c SC on Nam Gamma Laws Regular Expression gt NFA contquotd Case E E E2 By IH 3 FA M1 M2 with ME LM1 and LE2 ZAMZ Construct the following NFA M Case Unmark nal states in M1 M 5 F 33 2 c SC on Nam Gamma Laws Lecture 03 18 CSC 473 Automata Grammars amp Languages Regular Expression gt NFA contquotd Case E E By IH 3 FA M1 with ME Ml Construct the following NFA M C so on New Gamma Laws 9222007 Case C so on New Gamma Laws Example Reg EXp gtNFA baa C so on New Gamma Laws 0 a 0 Not very economical Lecture 03 19 CSC 473 Automata Grammars amp Languages 9222007 Regular Expressions Applications Regexp used in various development tools qedrlnleracllve text editor ls version Lampson amp Deulsch1987 Regexp added by Ken Thompson Bell Labs ca l968 Regexp compiled into NFA l machine code Rabiancotl idea used to scan on the lly One at new sow me patents Ollspnng ad by Ken lor Unix Many otherslollowed am viaxsamqadx grep egrep 7 pattern Search W a ilie Shelli command ill le interpreter lexr leXical analyzer generator sedr HOl lrll lleraCllVe stream editor awkrpallem Scal mll lg and prOCeSSH lg language perlrpallernrdriven programming language C so on Autumn39s Gamma Laws Applications cont d Regular expressions patterns meaning Mregexp matches gt1 r r matches gtO r N matches 0 or 1 r r matches r then 5 rs matches r or s r l 5 match literal c c match beginend line A 5 match any char group exprs 5 character ist abc negated char list Aabcm c scouAmnmu Gammath 59 Applications Examples 7 079 nonemptydigit strings optional sign A 079 any char except digit reference citations in a paper gAl d delete blank lines g d delete lines with a blank Ex match is always 1 leftmost and 2 longest file abcddddef Vi Sdx gt xabcddddef sdx gt abcxef Ex csh sort roll175 l egrep quotc SClMATIl l pr C so on Autumn39s Gamma Laws Lecture 03 20 tdnquot nchar nword nlrne return 0 l c SC 073 Autumn Gammath 52 L Regular ltgt L Denoted by a Reg Expr We39ve defined regular as meaning recognized by a DFA equiv to rec by an NFA This equivalence result is known as Kleene39s Theoremquot We39ve already shown the direction we constructed an NFA from a regular expression Using RabinScott we could convert this NFA to a DFA Now we show the 2 direction given a DFA M construct a regular expr E with LM LEr Thm There is an algorithm that given a DFA M computes a regular expression E such that LM LEr PfLet M 422 5 SIF beaDFA If l Q l 1 1 wecanchoose Q 1 2 n and S l c 5cm Autumn39s swam 53 Lecture 03 21 CSC 473 Automata Grammars amp Languages 9222007 Kleene s Theorem cont d Define fork n1 Rf X i X Hg X1 re H45 x5 Hj s for some 5 2 o with alllt k R is the set of stringsx labeling the deterministic computation paths from node i to nodej that use only those intermediate nodes in 12 k7 1 So R11 uses no intermediate nodes and R12 represents all possible path labels from itoj Picture x 2 lutermedlate nodes 1n L krli c 5cm Autumn39s swabMs 5 Kleene s Theorem cont d Lemma Each Rf hasaregular expression denoting it PfofLemma By induction on k Base k 1 1 7 lta 1aj 1 j 8 U a i 51 a 1 1 j 1 and these have reg exprs of form a as or s a1 as MAssume the Lemma is true forklH Consider R2 The new node in use is node k All paths in RS either do not enter k or else go thru k one or more times Picture c 5cm Autumn39s swabMs 55 Kleene s Theorem cont d All paths in Rf either do not enter k or else go thru k one or more times So c sconAmnmu swabMs 66 Lecture 03 22 CSC 473 Automata Grammars amp Languages 9222007 Kleene s Theorem cont d Rfl Rf u Rfk r 12ka r Rf By lH and closure properties this is regular e To finish the proof of the theorem observe that MM U ngl and so by closure propefr gs LM is regular e Note Sipser text uses a different algorithm employing the concept of generalized NFA N FA that have regular expressions on their edges See Examples 166 and 167 57 c SC on Autumn39s Gamma Laws EX Kleege s Theorem a a 803 R32 R R R32ltR2gtR2 212 3 a R R32 RLltR31gtR2 R21 8 a R R2 mm R21 b Rf2bsaga ba b R2 sabsa bsaba b R a b a bs a ba b s a 23562 a bs a ba b N g RR R3 a ba ba b c SC on Autumn39s Gamma Laws Text Algorithm uses Generalized NFA R110100O c SC on Autumn39s Gamma Laws Lecture 03 23 CSC 473 Automata Grammars amp Languages 9222007 Algebra of Regular Expressions 3 an algebra for symplifying regular expressions Can use this algebra to consiruct RegExps from FSA rssr rstrst rrr r r rstrst reerr r r rst rs rt rst rt st e rquotr rquotrrquot rquot e rr rs rs C so on Autumn39s Gamma Laws Solving Regular Expr Equations Can solve linear equationsquot with regexp variables X aX b aagtltbbazgtltabb a2aXbabba3Xa2babb X a b Check aa b b aa b b aa eb a b El Ex 1 A b XaXbY 0 Ye 9Xab C so on Autumn39s Gamma Laws Solving RegExp Equations cont d ExNFA9 RegExp e 1 0 A 0A 18 2 B 15 0c 0 C 0A 18 iehme B 1 06 0 o A 0A11 oc2 C 0A 11 oc i ehmc c 11 OJ 0A A 0A 11 011 0 0A 2 O 11 Ol 1 0 OA 2 o 11 011 0 o Slmpllfy uslng reg algebra O 11301130 O 2 11301130 O ll OfO A also 0 Gaussuordanelirninalion amp backrsubslilulion C so on Autumn39s Gamma Laws Lecture 03 24 Slide 71 2 Analog in real numbers X aX b a lt 1 X aX b 1 aX b X 11 ab 1 a aAZ b Peter J Downey 9112007 CSC 473 Automata Grammars amp Languages 9222007 Closure Properties A class of languages is said to be closedunder an operation if applying that operation to members of the class results in a language that is again a member of the class Example the regular languages are closed under the operations of union concatenation and Kleene star Thm The regular languages are closed under intersection and complementation Pf Complementation Let L LM where M Q Zr 5 Sr F is a DFA Then the FA F4 Q 2 3 s F is also deterministic and Sr W FLUX 8 ltgt Sr W PEN 8 80w leads to a non accepting state in M cgt w leads to an accepting state in F4 So m 2 7 mm c sconAmnmu swabMs 73 Closure Properties cont d Intersection Let L I be regular By DeMorgan39sIaw L o L2 E u Li 4 Since the regular languages are closed under complementation and union the resultfollows e C so on Autumn39s aims Laws Closure Properties cont d Another proof of closure under H illustrates the technique called crossproduct constructionquot See Sipser text Theorem 125 Thm The class of regular languages is closed under the intersection operation Pf Assume r LM M 012 5151171 and L2 rmz M2 02 22 52 52 F2 where the automata are deterministic Constru on Construct a crossproduct machinequot Mas follows M Q X 02 21 u 22 5 X 52 5152 F X F2 where the transition function is defined by 5 X 54 q qz a 2th a my a 4 Machine M simulates the two given machines in parallelquot keepineach machine state in one component of lt11 lt12 45 cscuaAu u math Lecture 03 25 CSC 473 Automata Grammars amp Languages 9222007 Closure Properties cont d Verification By an easy induction on lxl can show that qu qg I X PM 10 102 I 8 lt3 qu X I L pu 8 A 012 X P241102 8 D Therefore forapair of final states f1 6 F f2 6 F2 SjI SQ I X PM ij f2 I 8 ltgt s x t L m e A s2 x I f2 8 This says that X e LM ltgt X 6 MM A X e LM2 iethat LM LM m LM2 u c 5cm Autumn39s swabMs 75 Closure Properties cont d Defn A homomorphismh is a function that maps each symbol of E a 32 an toastring over some alphabet A Le Maj ijhGQ WQIV 7 Ma w n The homomorphism is extended to operate on strings characterby character ie hCC2 Cquot hChC2 MC It is further extended to languages elementwise ie hL MW w e L Thm f Lis regular and h is a homomorphism then hL is regular PfAssumeLis recognized bya DFA M QI XI 5I SI Fr c sconAmnmu swabMs 7 Closure Properties cont d Construction Constructthe machine M Q 2 I3 5 F where for each transition in M a Ma put into Mh the transition 0 9 An easy induction establishes that SI VIM Mg 6 ltgt SI MW i LAqI 6 I from which it follows that MM hLM u c 5cm Autumn39s swabMs 739 Lecture 03 26 CSC 473 Automata Grammars amp Languages 9222007 What is Not Regular FA have a very limited computing ability They cannot for example recognized strings of wellnested parentheses or wellformed arithmetic expressions or even the language of strings of the form ww having two copies of the same substring How can we show some languages are notregular We will give a property that all regular languages must have called the pumping property Then to show that a language Lis not regular we argue that it lacks this pumping property c SCMBAmmuu Gammath 79 Pumping Lemma Thm Pumping Lemma for Regular Languages Suppose thatL is an infinite regular language Then 3p Vw w E L AW 2 p EXyzwxysz SAXygp AVi 2 0 Xylz E L lAll tlrllte languages are regular so only lnllnlle languages are 0t lrlterest c sconAmnmu Gammath m Pumping Lemma English Thm Pumping Lemma for Regular Languages Suppose thatL is an infinite regular language Then there is some number p called the pumping length such that ifw is any string in Lwith iWin then w can be factored into 3 substrings w xyz that satisfy the following 3 conditions i y 9 y is not empty ii Ixyl Sp the prefix and pumped part are short iii for everyiz O xy z E L pumped upquot and pumped downquot i 0 versions of the string must also be in L lAll tlrllte languages are regular so only lnllnlle languages are 0t lrlterest c sconAmnmu Gammath 5 Lecture 03 27 CSC 473 Automata Grammars amp Languages 9222007 Pumping Lemma cont d Pf Let M Q 2 6 s F be a DFA recognizing Land letp be the number of its states Let W ala2 a be an input string of length n where n 2 p Let r1 r2 quot r rw be the sequence of states thatM enters while processing w so that rm 6r1 al for l S i S IL This state sequence has length n1 2p1i Among the firstp1 states of this sequence at least 2 must be the same state pigeonhole principlequot Call the first of these 2 r and the second rk r Because rk r occurs among the firstp1 places in the sequence r1 r2 quot r r we have thatkSp1A Define the following substrings of w X a1 7751 y 51 aka 2 ak a c scouAmnmu Gammath Q Pumping Lemma cont d Picture From the picture we see that there is an accepting path from s r toafinal state rm1 for all the strings of the form xy z i 2 0 Also since j 1t k itmust be that y i 8 Furthermore k S p 1 so lxyl S p c sconAmnmu swabMs 3 Non regular Examples Ex L lak2 k 2 O isnotregular Pf By contradiction SupposeLisregular Then by the Pumping Lemma 3Xyzx aPy a q gt 0z ar NH 2 O aJD aq ar e L Then itfollows that V17 2 0 P q 39 n T r isaperfectsquare Thisisimpossible For suppose prqn0 k fora k0 solargethat 2k01 gt q Then prqnol k qltk2kolkol2 Hence p I q no l falls in betweenquot perfect squares a contradiction e c sconAmnmu swabMs 5 Lecture 03 28 CSC 473 Automata Grammars amp Languages 9222007 Non regular Examples cont d ExL w wR w e a bf is notregular Pf By contradiction SupposeLisregular Then by closure properties of the regular languages L1 L m a bba is regular Now L1 la bba n 2 0 We show Ll cannot be regular which provides a contradiction If Ll isregular then there are substrings X Y Z with y i g suchthat VI 2 O xy z G Ll Case 1 y is entirely in the as Assume it is in the as before the 2 b39s The other subcase is symmetric Then X apy aqz arbbas q gt O and p q r s Butthen aparbbas e L where p I lt S Thisisacontradiction c SC 073 Autumn amalgam 35 Non regular Examples cont d Case 2 y contains a b Then Xy3Z has more than 2 b39s and so Xy3Z E This is a contradiction Contradictions in all cases 2 contradiction to the assumption that L1 isregular So Ll isnotregular EX L anbn n 2 O isnotregular SeeText Example 173 EX B w w 15 a wellrnested string of parentheses is not regular Pf Suppose B is regular Then sois B B 391 if Mn 3 D Z 0 asisitshomomorphicimage la b n 2 O Contradiction e c sconAmnmu swabMs 35 Decision Problems For a propertypredicate P the decision problem for P is Given 1 Question is Pu true7 Ex Given DFA M is it true that LM Q Thm For DFA Mall the following decision problems are solvable ie there exists an algorithm to decide the question for any input Given Question 1 MW w E LM 7 2 M LM a 7 3 M LM 2 7 4 MM LMQLM 7 5 MM LMLM c scouAmnmu Gammath 27 Lecture 03 29 CSC 473 Automata Grammars amp Languages 9222007 Decision Problems cont d P Assume given DFAs for inputs 1 Trace w through Mt Yes if leads from s to some 11 E F 2 Yes if there is some 11 E F reachable from s 3 Convert M gt M UM 2 ltgt UM Q 4 HM Q LWQ ltgt LWQVW L041 Q 5 Use 4 twice c SC on Autumn39s Gamma Laws Lecture 03 30
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'