Class Note for C SC 473 at UA
Popular in Course
Popular in Department
This 21 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 17 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 9302008 Theory of Computation Lecture 04 ContextFlee Grammars and Pushdown Automata c sc m Antonina amum a Language Backus Naur Form Grammars CFGs Algol 60 Algol 68 first blockstructuredquot languages ltprogramgt ltblockgt ltstatementgt 7 s i ltblockgt ltblockgt begin ltlistgt end ltstatementgt ltlistgt i ltstatementgt ltlistgt Ex begin 5 begin 57575 end 75 end Grammar Start variabie S i G FAB ZSybr r S gt s T 6 5 2 B terminate B e bLe r on e as mg an V L e s L R ya0 L a 5 ns Grammars are Generators a bbsee bse hbSee 2 n 0 lose 2 bEe 2 thee 0 U P 2 E 2 bLe 13135 Lee 2 r U a bs Le 2 7 135 Le gt hB Le gt bbLe Le gt 39 bSSe 2r bsSLe 2r 2 yields or derives in one stepquot Appiy one production to one vanabie W the string nondeterministic C so on Autumn39s Gamma um CSC 473 Automata Grammars amp Languages 9302008 A Particular Derivation One possible derivation Variable being rewritten at each stage is underscored g 2 g 2 bge 2 b5 e 2 b55 e 2 135 Se 2 b5 5 Se 2 lug bLe Se 2 15 bLe e 2 15 bge se 2 15 12 Le se 2 15 135 Le se 2 15 15 g Le se 2 15 bs 5 Le se 2 15 15 5 ge se 2 15 15 5 se se 15 15 5 Se se E LG two choices at each derivation step Which Variable hohtermihal to be rewritten Which rule with that variable as LHS to be applied7 All possible terminal strings obtainable in this way make UP L G c sconAmnmu swabMs Why CFGs Most natural or artificial eg programming languages are not regular LG n b se tb se i n 2 1 We know that the latter language is not regular so Ex 3 programs mainllll mainlHibmainllllllllpr camaimn mainlquot i n 2 1 c sconAmnmu swabMs 5 Derivation Parse Tree P I j b e i L r S s 39 L I 39 s S L I yieldfrontierterminal string S 39 bs bs 5 se se 5 C 5c M Autumn39s Gammath 5 CSC 473 Automata Grammars amp Languages Derivation Parse Tree P I E b e I i L s S L C so on Mimi Gamma Laws 9302008 Derivation Parse Tree cont d I r 5L 5 s S L 71 u 11 12 L IS 13 14 s S L g 515 I S C so on Mimi Gamma Laws ContextFree Grammar Defn 22 A contextfree grammarG is a 4iuple G V Z R S i V is a iiriiie seli lhe varabes 2 2 is a iiriiie sei disiomi lrom Vi lhe ermines 1 R is a lll ille sel ol rues 01 We lorm AHWAEVWEVUE s E V isihe srarrveri ebe Ex strings wiih balanced parentheses Formally 390 ew lbth RBgt BgtBBBgtB Ex informally G01B gt s l B gt BB l B gt B Variables uppercase Terminals lowercase C so on Mimi Gamma Laws G0V121Rr5 Elil VlBl 513 CSC 473 Automata Grammars amp Languages Yields amp Derives Relations Defn The relation yields derives in 1 step 2VU2 gtltVu2 is defined as follows if A 2 w is a rule in R then Vii V E V U 3 uAV gt uWV Defn derives in k steps 2 Defn derives f in otherwords u 2 V iff u V or 311 Buziw ukd u 2 u1 2 uzm 5 UH 5 v Defn A derivation ofn steps from U0 is any sequence of strings satisfying L10 2 L11 2 L1239 2 uk C so on Autumn39s awe um 9302008 Language Generated Defn The language generated by G is the set of all terminal strings derived from S LGwiwez As w A paniederiverioms one that starts with S and ends W a nonrlermina string containing variables W V Ex saaAsia AasbAissiba Partial s 2 355 2 aSbAS Terminal orlerminaled s 2 ags 2 asbAs 2 aang 2 aabbas 2 aabbaa C so on Autumn39s awe um Derivations and Parse Trees Ex G01BgtslBgtBBlBgtB g the sequence grow dillerenlly C so on Autumn39s awe um leftmost E 2 BB 2 513 2 5 B 2 3 2 B 2 UN rightmost E 2 BE 2 135 2 B 2 B 2 B 2 UN B B BB BB B B B B B B B BBB B lt B gt Ase i393 New B gt l3B B B B 8 8 B 8 Notice completedlermineledperse tree is the semelor both derivationsilnougn CSC 473 Automata Grammars amp Languages constructible from D nodes are visited C so on Autumn39s Gamma Laws Derivation gt Parse Tree Proposition 1 For every terminated or partial derivation DISgtL1gtL1239gtL1quot there is an unique parse tree T with frontier uquot Proposition 2 For every parse tree T in G and any traversal order that is topdown visits parents before children there is an unique derivation for the frontier ofT from S and it is constructible from T Corollary 3 For every parse tree T in G there is an unique leftmost deriva on constructible from T Pf Preorder traverse T expanding variables as their 9302008 f11 quot1 t mlt EX Leftmost Derivation m m x W HV x w HV EgtETlT TgtTFlF FgtElX x W H m x W H H x w C so on Autumn39s Gamma Laws 1quot3 i lt N 6 3911 7T F12 8310 9F X C so on Autumn39s Gamma Laws EX Leftmost Derivation 1 Preordertraversal l 13 F E14 I 15 17 16 F18 17F gtl I X CSC 473 Automata Grammars amp Languages 9302008 EX Le most Derivation cont d My rnr 2FF i f tEMF WV if E T T l I GTMF I T F F l I X X imzrtrtnr I I F X XFTF stxmtriw X tmxtnnr txmtxny 16 c SC on Adam Gamma him EX Le most Derivation cont d xxxE i i E xxxtzr i F I xxxrrl f11 1 mlt xxxrrl xxxxr x w HV rd xxxxr xxxxx x W H H x w c SC on Adam Gamma him Syntactic Ambiguity E terminal string a a a E EE 2distinctparse treestor same I I terminaistring a a gt Egta gt 2 distinct iettmost derivations tor same terminai string a E E a a E Lettmostderivation t gt parse tree a a x a Hort E E ACFG is unembiguousc I viiezta w nas an unique parse tree unique iettmost derivation a gt Egt EEgt a Eaa a a a c 5cm Adam swam CSC 473 Automata Grammars amp Languages EX Ambiguous Grammar English ltSemgt4ltNPgtltVPgt ltNPgt2ltNgtlltAdjgtltNgt ltVPgt4ltVgtltOhlgtlltVgtltMvPgt ltAvagt4ltAdvgtlltAvagt ltAvagt4ltPreDgtltOhlgt ltomgt4ltmpltm ltNgt4fmifl fliesl C so on Autumn39s Gamma Laws 9302008 Fruit flies like a bananaquot fruit flies like ltlidjgt ltllgt a banana ltSentgt ltN Pgt ltVPgt I ltNgt ltVgt IltAvagt C so on Autumn39s Gamma Laws ltomgt4ltmpltm ltl1djgt ltilgt ltilgt IltObjgt gunman I fruit flies ltPrepgt ltObjgt I l like ltAdjgt ltNgt l a banana ltSemgt4ltNPgtltVPgt lt Hmmixm ltSentgt ltVPgt4ltVgtltOhlgtlltVgtltMvPgt ltN p ltV p ltAvagt4ltAdvgtlltAvagt I gt 2n E IgtNFAN gt lt Chomsky 1958 called these Type aquot from finite automata to rightlinear grammars and conversely C so on Autumn39s Gamma Laws Thm Lis aregularlanguageiff ZLG for some right linear grammar G There are algorithms for convening Right Linear Grammars amp Regular Languages DFA M 3 conversion algorithm Reg Expv Righlrlinear Grammar Defn A CFG is rightIineariff each rule is of one the forms AgtwB or Agtw where A B are variables and w E 2 CSC 473 Automata Grammars amp Languages Right Linear amp Regular cont d Pf Assume LLM where M Q E 5 S F isa DFA Construct G Q E R s witthaving rule p gt aqifin g andrule p gt 8 if p isafinal state mmpe rrraquw iff p 3 a manq P easyinduction on n The proof direction follows since 5 wi 4q 8 iff s 3 wq 3 w I PfAssumeLLG where G V E R S isright linear ConstructNFA N V E 5 S f where f g V isanew symbol Bhas the transition W a ifinR A a wB and transition M if A a w c 5cm Autumn39s swabMs 22 9302008 Right Linear amp Regular cont d Claim AU 36 ij1 36 W1W2A2 36 3 iff Ag W1 WnHHW W2 WW7 MAM 8 w rwA s 1quot 11 Pf easy induction on n The proof direction follows since S 3 WA 3 WX iff S VIM MA XI f 8 I c 5cm Autumn39s swabMs 23 EX Rig ht Linear 9 FA ExGSgtaAlb AaaBldS B dA b 996 ExM b b ab GM q0 gt aqo lbq l 8 qr aqgibqug gt a l b q2 q2 q2 useless rulesican be eliminated c 5cm Autumn39s Gmdbhws 2 CSC 473 Automata Grammars amp Languages Pushdown Automaton Defn 212 A pushdown automaton M is a 6iuple MQIZIF6SIF 2520 Q is aiirme sen ihe states 1 1 u s 2 is a iH Hie ihe inputsphaber F is a me sei ihe stack aphaber 6 1 Q x Z x 1quot i Q x 1 5 isihe transiton function S E Q isihe stansrare F g Q isihe seioi acceprmnaosrares c SC on Nam Gamma Laws 9302008 Eusthwn Automaton seen 0 come a a 11 an inpmsz ax s 2 cunem inpui smboi Finite Conh39ol A1 5 F siacksr Top Eonom no end mavkevsuppiied coniiguraiion pralazag VA1A2A3 siaie vest oi inpul Stack c SC on Nam Gamma Laws PDA cont d E Initially SEESDI w sian Siaie coniiguraiion s w s c SC on Nam Gamma Laws CSC 473 Automata Grammars amp Languages 9302008 PDA cont d c SC on Autumn39s awe Laws PDA cont d Canhavea 8X 81 8 emove consume no input 5 YE 5p 8 X p ax X06 i q ax Ya Popmove erase top stack symbol 6 me 5p a X p ax X06 Hq x at Pushonly move ignore stack q Ye 5p a s p ax X06 Hq x Ysz Any combination is possible q me 6p e s p ax X06 big ax X06 c 5cm Autumn39s swabMs 25 PDA cont d Finally Finite Conh39ol Conliguralion f s a Defn M recognizesw iffforsomef e F and some I E 1quot s w 8 i l4f 8 a Dent LM w M accepts w c sconAmnmu swabMs 3 10 CSC 473 Automata Grammars amp Languages Example PDA Recognizer for L WCWR l w e a bf FlArBl F lfl s abbcbba 2 l abbcbba 5 l bbcbba A5 quot39 p cbba BBAS l q bba BBAS l q be 8A5 l quot39 q a A5 l q 2 5 l f 2 2 f accepls s acb 2 l p acb 5 p Cb A5 ltq b As4 blocked c SC on New aims Laws does nol accepl M 92F6SF QSpqf 2labcl 9302008 Last example palindromes with centermark was a determinis c PDA DPDA N P DA for L wquot lwe lab 5 aa 2 l D ea 5 l p a A5 l P 2 AAS H I 5 M5 does nolaccepl q blocked 5 aa 2 l D ea 5 I p a A5 l q an A5 l 2 5 l f 2 2 c SC on New aims Laws Example PDA w nondeterminism Example PDA Recall wellnested parentheses 0 00 GuzsaslBaBBlBa pws 1 2225 v preflxes x of w lxl 2m lwl lwl DPDA c SC on New aims Laws 2 HA 1fthen 1 A gt2 um thenr 11 CSC 473 Automata Grammars amp Languages CFG gt PDA cont d Given 6 V Z R 5 construct P Q 2 1quot 6 gm F S a es Q qmm Camp Cam npm a phabe z S ack a phabe V U 3 U lt5 S ar s a e qstaxt Accep s a es F quark Transmonmncnon nmahze mack 6q5tm 2 2 lt qlmp 55 gt Swmu a eru ea VAaa e 61qu 2 A lt qm a gt Checkomerrmna s Va 5 2 Saw a a lt qm 2 gt De ec nuH s ackampaccep 6qw 2 5 lt qu 2 gt 2 2 gt 55 2 5 gt 2 a We 3 aa sA gt 11VA awe R 37 c SC on Nam Gamma Laws 9302008 CFG gt PDA cont d Ex GUISgt SgtSSSgtSSd gtS asas SSgt asass ddgts 85 assd sysas S 1 KADI ltgt gm XLI SS I qu u A115 2 s 2 w a ltq1 opws5 mam MS Hqu s 2 c SC on Nam Gamma Laws CFG gt PDA cont d Q g qsmu ssddsd 6 E L QM ssddsd 5 9 3L QM Ssddsd gss sgds gtL qlccp ssddsd SdS qmp sddsd EdSS SSdeS 2L qmp desd gsddss gm ddsd EddSS Ssdd 2L gm ddsd gdSS qlccpr de 55 ssdds d gtL c SC on Nam Gamma Laws 13 CSC 473 Automata Grammars amp Languages CFG Igt PDA cont d Q 2 qmw dr d qmp 14 qmp 6 6 5 l ssddsd qaccepu 8 s Ssddsd E HG ssddsd 6 EH S 2 ssddsd qstm ssddsd s gacceptzl 8 8 CFG leftmost derivation PDA computation c SC on We awe Laws 9302008 PDA Igt CFG Lemma 227 There is an algorithm for constructing from any PDA P a CFG G such that LG LP Pf Given a PDA P Q 2 1quot 3 go F we can convert it into a PDA with the following simplified structure it has only one accept state F qaccept as add etransitions from multiple accept states f gimpt it empties its stackjust before entering the accept state wee Loop on astate thatJust pops gm gt gm X E 1 each PDA transition is either a pure pushquot a 8 gt X or a pure pop a X gt s introduce new intermediate states c SC on We awe Laws PDA gt CFG cont d alxay becomes aXgt gtY 3868 becomes a gtX Xgt Idea of proof constructGwith variables Am for each p and q in the set of states Q Arrange that if Apg generates terminal string x then PDA P started in statep with an empty stack on input string 1 has a computation that reaches state 11 with an empty stack And conversely ifP started in statep with an empty stack has a computation on input string 1 that reaches state 11 with an empty stack then Am gtG X How does P when started on an empty stack in state p operate on an input string 1 ending with an empty stack in state 11 First move must be a push a 8 a X Last move must be a pop 1 X a g c scouAmnmu amalgam 39 2 14 CSC 473 Automata Grammars amp Languages PDA gt CFG cont d 1 sack never emp es pq Stack height Trace computation of P on 1 starting in statep with empty stack and ending in state qwith empty stack A 5 aArsb Fig 1 9302008 PDA gt CFG cont d 2 sack emp es somwhere W at rq Stack height Amity Aq Q 2 C so on Nam awe Laws Trace computation of P on 1 starting in statep with empty stack and ending in state qwith empty stack A 5 A A Fig2 inpul PDA gt CFG cont d rulesin R VP q e Q V e Q Am a APIAIq Vpe Q Appas o then Apg gt ailer C so on Nam awe Laws Vp q r s 6 Q VX e F Va b e 25 ii a e 5 e a a Xa Construction Given PDA P Q 27 1quot 5 C10 qweng construct G V 2 R Aqua with the following 15 CSC 473 Automata Grammars amp Languages PDA gt CFG cont d Claim 230 lprq 5 x then p x g F q a g Pf by induction on a derivation in G length 16qu gt X Base k1 The onlyderivations oflength 1 are App 3 5 and we have p 8 8 1 p 8 8 Step Assume IH true for derivations of S k steps Want Claim true for derivations of k1 steps Suppose that Am if X The lstderivation step is either of theform AW gtG aAer or Apg gtG Ami1m Case Am gtG 31le Then X ayb with Ars gt y SolH 2 r y 8 1 s 8 8 By constructionsince AW gt a2er isarule of G c SC on Nam swat Laws 9302008 PDA gt CFG cont d VX r X E 31p a ampq 6 E 55 2 X p x 8 3915 r yb X 1 s b X 3915 q 8 8 Case A 5 A 2A Then x yz with API gtk y amp Am gtk z SolH 2 plyne 1 nae amp has 1 1 QISIS Putting these together pyz rzs rze v g Lash c SC on Nam swat Laws PDA gt CFG cont d Claim 231 If p X g F q 5 5 then AM gt X Pf by inductign on a computation in P of length k p x 8 Ip q 8 8 Base k0 The only computations of length 0 are p X 8 1 p 8 8 wherexe By construction 1 AW 25 g Step Assume IH true for computations of S k steps Want Claim true for computations of k1 steps Suppose that p X 5 Fig q 8 8 Two cases either the stack does not empty in midst of this computation Fig 1 or it Becomes emptyduring the computation Fig 2 Call these Case 1 and Case 2 c SC on Nam swat Laws 16 CSC 473 Automata Grammars amp Languages PDA gt CFG cont d Case 1 See Fig1 The symbol Xpushed in the 15 move Is the same as that popped in the last move Let the 15 and last moves be governed by the pushpop transitions r X E 513 a E ampq E E 55 b X By construction there is a rule in G Am gt aArsb Letxayb Since r y X Ff s g X then we musthave r y g pig 5 g g ByIH Then Ars 8 y Using Am 8 aAer we conclude AW 8 ayb X C so on Autumn Gamma Laws 9302008 PDA gt CFG cont d Case 2 See Fig2 Let rbe the intermediate state where the stack becomes empty Then 3Y1 Z X YZ x plyne a has amp has a cage BythelH APr gt y and AM gt Z Since by construction there is a rule in G of the form AW H AprAlq V 7 then qu gtG AMA gtG yz 7 X n C so on Autumn Gamma Laws PDA gt CFG cont d 9 P gt imp F gtA Q ltsqfgt A 2 AS yy up w w E a Yisawellrbalanoedstringofparentheses Rules of G e e 1 pushpop pairs 15 kind it 2 a s A a H 0 H H A as C so on Autumn Gamma Laws 17 CSC 473 Automata Grammars amp Languages PDA gt CFG cont d Note If P 1 ft 13 1 p unreachable then P I X i App 3 X Q abbreVIated App Q Such variables are useless all rules involving them on left or right sides can be eliminated as useless productions For this grammar qu Q A Q A Q 2 Rules of the 2 d nd with useless rules removed only 1027 survive in the order sqf ASS HASSASS A HA A A 14224 Asq aAquqq Aqf aAqf ff Asf aAssAsf Aff AffAff ASf HASquf Asf aAszff c 5cm Autumn39s Gammath 52 9302008 PDA Igt CFG cont d 2 Rules of the 3Yd Kind A55 as An H8 Aff H8 Combining all rules with same LHS Ass HAssAss l 9 Asq HASSASq l AS A Asf all Aqq ll l AssAsf l Aquqf l Aszff Aqq lAqq l Aqquq l g Agf HAqquf l Aquff Aff AffAff l g c sconAmnmu swabMs S PDA gt CFG cont d Simplify easy to see that A55 8 Aff 8 Substituting this into rules A aASq i ASquq A5f all Aqq ii i A5f i Aquqf i A5f A lAqq l Aqquq l g HAqquf l Aqf Eliminateuselessruleslike X gt X Asq aASquq A5f ll Aqq ii i Aquqf Aqq mg i Aqquq i e Aqf HAqquf c SC 073 Amman Gammath 5 18 CSC 473 Automata Grammars amp Languages PDA gt CFG cont d Another kind of useless rule Asq Agf generate no terminal strings Eliminate these variables any and rules mentioning them Final simplified grammar is 17Sf all Aqq A99 HlAqq l Aqquq l g Note chose to use endmarkers for clarity but these could have been 9 input symbols can be anything in Es leading to the familiar grammar ASf HAW A99 HlAqq l Aqquq l g c SC on Nam Gamma Laws 9302008 Closure Properties Regular Ops The CFLs are closed under U Pf Homework Intersection The CFLs are notclosedunder intersection Example Consider the two CFLs I a b c ln20L2a b ln20 c Then L1 0 L2 a b c l n 2 O4 We will later see CF Pumping Lemma that this last is notaCFL e However if L2 is regularand L1 is CF then L1 0 L2 is CF c SC on Nam Gamma Laws Closure Properties cont d Thm The class of CFLs is closed under intersection with regular languages Pf Assume L ma P QHZNF 6151171 and R LM2 M2 02 22 52 52 F2 Construction Construct a crossproduct pdaquot M as follows M Q X 02 21 u 22 1 5 SJ2 F X F2 where the transition function a is defined by 10 p2 Y s R q 612 y a X provided 13 Y s aquotqa X and P2 52012 a Machine M simulates the two given machines in parallelquot keeping each machine state in one component of the compound state c SC on Nam Gamma Laws 19 CSC 473 Automata Grammars amp Languages 9302008 What is NotConteXt Free PDA have a limited computing ability They cannot for example recognize repeated strings like ww or strings that count in more than 2 places such as aquotbquotcquot We will show that some languages are notCF using a CF Pumping Lemma which gives a property that all CFLs must have Then to show that a language L is not CF we somehow argue that it lacks this pumping property Closure properties of CFLs can sometimes be used to simplify nonCFLs and make a pumping argument easier c sconAmnmu swabMs 5 CF Pumping Lemma Thm Pumping Lemma for CFLs Suppose thatL is an infinite CF language Then 31 VW W E L Alwl 2 p gt 3U V X y z w uvxyz vy 8 lvxyl S p Vi 2 0 uvixyiz e L For comparison here is the Regular PL 31 VW W E L Alwl 2 p gt 3Xyzw Xysz 8 Alel 5 pVi 2 0Xyiz L c sconAmnmu swabMs 59 CF Pumping Lemma cont d Pf Let L 7 is LG where CFG G is a CFG in Chomsky Normal Form Text Theorem 29 Le a CFG in which all rules are of the schematic forms AgtBC or Agta 1 9 If W E LG is sufficiently longquot then any derivation tree Tfor w must contain a long path more precisely Claim 1 If the derivation tree Tfor W has no path longer thanhthen lw i s 2 quot S Pf Induction on h Baseh 1 Only possible tree is I and la i 2 Step Assume h gt 1 LetThave all paths 5 h and be of form in CNF a c sconAmnmu swabMs 6 20 CSC 473 Automata Grammars amp Languages CF Pumping Lemma cont d S t w St Then T1 T2 have all paths oflength h 2 l BylH lslS 2 2it l s 2H which implies lw l s 2 quot Conversely if a generated string is at least 2h long then its parse tree must be at least hl high Ghas lVl variables Choose 10 ZlVlHt If w E L and lwl 2 p then Claim 1 2 any parse tree Tfor w has a path of length at least M 2 Such a path has at least M 3 nodes some variable aggears twice on the path note the leaf node is a terminal C so on Autumn smut Laws 9302008 CF Pumping Lemma cont d Picture 2 lvl 2 height 2 2 lvl 3 nodes 2 2 lvl 2 variables 2 repeat Choose M 3 ht s M 2 2 2 W P tututu W U V X y Z W lvxyl 62 p C so on Autumn smut Laws CF Pumping Lemma cont d 1 Center portion is not too long lVXyl S p 2 Pumped portion not empty Vt y cannot both e R x 5 V X y or R B c in ONE no Variable generatese 5 x v x y 53 C so on Autumn smut Laws 21 CSC 473 Automata Grammars amp Languages 9302008 CF Pumping Lemma cont d 3 Pumped strings in L the following are all parse trees A A a A LIVVnyz A u VVV x yyyz V1 2 O uV Xy z E L El LI X z c sconAmnmu swabMs 5 CF Pumping Applications Ex L a b c i n 2 0 is not a CFL Pf Suppose it is CF Then the Pumping Lemma 2 3p V WEL leZp gt 3 uvxyz w amp vy 6 amp V120 u leyiz EL Pick p as the constant guaranteed and choose n 2 p3 and w a b c uvxyz Vy i 8 Where is ny Cases Assume first that V at 8 an ab be c i u I v I x y z i l u l V l X y z I i u I v IXYZI i u I v i x y z i i u I v i Xyz I i u I v i Xyz I c 5cm mu Gammath 55 CF Pumping Applications In cases13 LIVZXYZZ has an imbalance In case 4 it has a b before a In case 5 it has a c before b In case 6 it has an a after a c In any case there is a contraction to the pumped word being in L The casewhere y 8 is symmetric Contradiction CorThe CFLs are not closed under complementation PfLanquotc Ip qvq rvp ri isaCFL But 3 a b c a b d I 1 2 0 is notaCFL Therefore f cannot be CF Ex L a I 1 prime is notCF Proofsimilar to regular case Ex L a 2 H 2 0 isnotCF c sconAmnmu swabMs 66 22
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'