Lecture 10: Exam 1 Context-Free Languages Contextually

Lecture 10:ContextContext-FreeLanguagesContextuallyExam 1 In class, next Thursday, Feb 28Problem Sets 1-3 Comments Covers:Exam 1Lectures 1-10Sipser Ch 0-2David Evanshttp://www.cs.virginia.edu/evansNote: unlike nearly all other sets we draw in this class, all of thesesets are finite, and the size represents the relative size.cs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 10: NDPDAs/CFGs/PDAsExam 1 NotesheetMenu For Exam 1, you may not useanything other than Are DPDAsequivalentto NDPDAs? Properties ofCFLs Equivalenceof CFGs andNDPDAs– Your own brain and body– A single page (one side) of notes thatyou create You can work with others to createyour notes pageLecture 10: NDPDAs/CFGs/PDAsLecture 10: NDPDAs/CFGs/PDAsPum Violapin tesgFor LemCFL mas3Language ClassesWhere are DPDAs?0n1n0nDescribed by DFA, NFA,RegExp, RegGramwwwR4Proving Set Equivalence0n1n2nwwgpinums P r RLsola teVio ma FLemA B A B and B ASets A and B are equivalent if A is asubset of B and B is a subset of A.CFbye d DArib Psc NDDeRegular Languages2G,Context-Free LanguagesLecture 10: NDPDAs/CFGs/PDAs5Lecture 10: NDPDAs/CFGs/PDAs61

Proving Formalism EquivalenceLR(M) the set of languages that can berecognized by some M { l l P(Σ*) and there is some m MProving FormalismNon-EquivalenceLR(M) the set of languages that can berecognized by some M { l l P(Σ*) and there is some m Msuch that L(m) l }such that L(m) l }A B There is an l P(Σ*) that is inLR(A) but not in LR(B)or there is an l in LR(B) but not in LR(A)A B LR(A) LR(B) and LR(B) LR(A)Lecture 10: NDPDAs/CFGs/PDAsLecture 10: NDPDAs/CFGs/PDAs70n1n0n1n2nwwR8LR(NDPDA) LR(DPDA)wwgpinum L ssPRla te a ForioVmLem0nwA LR(NDPDA)CFbye d DArib Psc NDDeRegular LanguagesG,To eliminate , we need to find some language L thatcan be recognizedContext-Freeby an NDPDAand prove it cannot beLanguagesrecognized by a DPDALecture 10: NDPDAs/CFGs/PDAs9LR(NDPDA) LR(DPDA)A { 0i1j i 0, j i or j 2i }Proof by contradiction.Suppose there is a DPDA P that recognizes A.It must be in accept states only after processing 0i1i and 0i12i1, α β ββ 1,1, α0, α α β Lecture 10: NDPDAs/CFGs/PDAs1, ε ε10LR(NDPDA) LR(DPDA)A { 0i1j i 0, j i or j 2i }A LR(DPDA)A LR(DPDA)2i transitions, consuming 0i1i1, εε, ε εε, εε, ε1, εSensible option 1: LR(NDPDA) LR(DPDA) LR(NFA) LR(DFA)Sensible option 2: LR(NDPDA) LR(DPDA) LR(NFA) LR(DFA)Lecture 10: NDPDAs/CFGs/PDAs0, ε ε, ε ε, ε εDescribed by DFA, NFA,RegExp, RegGramA { 0i1j i 0, j i or j 2i }i transitions, consuming 1i11Proof by contradiction.Suppose there is a DPDA P that recognizes A.It must be in accept states only after processing 0i1i and 0i12i21, α β ββ 1,12, α0, α α β 2i transitions, consuming 0i1iL(P’) {Lecture 10: NDPDAs/CFGs/PDAsi transitions, consuming 2i0i1i2i i 0}122

LR(NDPDA) LR(DPDA)A { 0i1j i 0, j i or j 2i }0n1nwwA { 0i1j i 0, j i or j 2i }A LR(DPDA)13Closure Properties of RLsIf A and B are regular languages then:AR is a regular languageConstruct the reverse NFAA* is a regular languageAdd a transition from accept states to startA is a regular language (complement)F' Q – FA B is a regular languageConstruct an NFA that combines DFAsA B is a regular languageConstruct an DFA combining DFAs thataccepts if both acceptLecture 10: NDPDAs/CFGs/PDAs15CFLs Closed Under ReverseGiven a CFL A, is AR a CFL?Since A is a CFL, there is some CFG G that recognizes A.Proof-by-construction:There is a CFG GR that recognizes AR.G (V, Σ, R, S)GR (V, Σ, RR, S)RR { A αR A α R }Lecture 10: NDPDAs/CFGs/PDAs17Regular LanguagesG,But, we know A' is not a CFL! (Prove using pumping lemma)So, there is no NDPDA that can recognize A', so there is noDPDA that can recognize A', so P' must not exist.Hence, P must not exist. This means there is no DPDA thatcan recognize A.wgpinum L ssPRla te a ForioVmLemCFbye d DArib Psc NDDeA' L(P') { 0i1i2i i 0}Lecture 10: NDPDAs/CFGs/PDAs0nDescribed by DFA, NFA,RegExp, RegGramProof by contradiction. If there is a DPDA P thatrecognizes A, we could construct a DPDA P' that recognizes0n1n2nAContext-Free LanguagesDeterministic Context-Free Languages: recognized by DPDALR(NDPDA) LR(DPDA) LR(NFA) LR(DFA)Lecture 10: NDPDAs/CFGs/PDAs14Closure Properties of CFLsIf A and B are context free languages then:AR is a context-free language ?A* is a context-free language ?A is a context-free language (complement)?A B is a context-free language ?A B is a context-free language ?Some of these are true. Some of them are false.Lecture 10: NDPDAs/CFGs/PDAs16CFLs Closed Under *Given a CFL A, is A* a CFL?Since A is a CFL, there is some CFG G that recognizes A.Proof-by-construction:There is a CFG G* that recognizes A*.G (V, Σ, R, S)G* (V {S0}, Σ, R*, S0)R* R { S0 S } { S0 S0S0 } { S0 ε }Lecture 10: NDPDAs/CFGs/PDAs183

Closure Properties of CFLsIf A and B are context free languages then:AR is a context-free language TRUEA* is a context-free language TRUEA is a context-free language (complement)?A B is a context-free language ?A B is a context-free language ?CFLs Closed Under UnionGiven two CFLs A and B is A B a CFL?Proof-by-construction:There is a CFG GAUB that recognizes A B.Since A and B are CFLs, there are CFGs GA (VA, ΣA, RA, SA)and GB (VB, ΣB, RB, SB) that generate A and B.GAUB (VA VB, ΣA ΣB, RAUB, S0)RAUB RA RB { S0 SA } { S0 SB }Assumes VA and VB are disjoint (easy to arrange thisby changing variable names.)Lecture 10: NDPDAs/CFGs/PDAs19Closure Properties of CFLsIf A and B are context free languages then:AR is a context-free language TRUEA*is a context-free language TRUEA is a context-free language (complement)?A B is a context-free language TRUEA B is a context-free language ?Lecture 10: NDPDAs/CFGs/PDAs20CFLs Closed UnderComplement? Try to find a counter-example{0i1i i 0 } is a CFL.Is its complement?Yes. We can make a DPDAthat recognizes it: swapaccepting states of DPDAthat recognizes 0i1i.Not a counterexample but not a proof either.Lecture 10: NDPDAs/CFGs/PDAs21Complementing Non-CFLs{ww w Σ* } is not a CFL.Is its complement?Yes. This CFG recognizes is:S 0S0 1S1 0X1 Opps!1X0 As Danni pointedout in class, this isX 0X0 1X1 0X1 badly1X0 broken.0 1 Weε willfix it next class So, we have found a pair: P, P where one is a CFLand the other is not. Thus, CFLs are not closedunder complement.Lecture 10: NDPDAs/CFGs/PDAs23Lecture 10: NDPDAs/CFGs/PDAs22Closure Properties of CFLsIf A and B are context free languages then:AR is a context-free language TRUEA* is a context-free language TRUEA is not necessarily a context-freelanguage (complement)A B is a context-free language TRUEA B is a context-free language ?Lecture 10: NDPDAs/CFGs/PDAsLeft for you to solve(possibly on Exam 1)244

Charge Thursday and Tuesday: someinteresting applications of CFGsLecture 10: NDPDAs/CFGs/PDAs255

4 Lecture 10: NDPDAs/CFGs/PDAs 19 Closure Properties of CFLs If A and B are context free languages then: AR is a context-free language TRUE A* is a context-free language TRUE A is a context-free language (complement)? A B is a context-free language ? A B is a context-free language ? Lecture 10: NDPDAs/CFGs/PDAs 20 CFLsClosed Under Union Given two CFLs A and B is A B a