Slide 1Exam 1Exam 1 NotesheetMenuLanguage ClassesProving Set EquivalenceProving Formalism EquivalenceProving Formalism Non-EquivalenceSlide 9LR(NDPDA)  LR(DPDA)Slide 11Slide 12Slide 13Slide 14Closure Properties of RLsClosure Properties of CFLsCFLs Closed Under ReverseCFLs Closed Under *Slide 19CFLs Closed Under UnionSlide 21CFLs Closed Under Complement?Complementing Non-CFLsSlide 24ChargeDavid Evanshttp://www.cs.virginia.edu/evanscs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 10: Lecture 10: Context-Free Context-Free Languages Languages ContextuallyContextually2Lecture 10: NDPDAs/CFGs/PDAsExam 1•In class, next Thursday, Feb 28 •Covers:Lectures 1-10Sipser Ch 0-2Problem Sets 1-3 + CommentsExam 1Note: unlike nearly all other sets we draw in this class, all of these sets are finite, and the size represents the relative size.3Lecture 10: NDPDAs/CFGs/PDAsExam 1 Notesheet•For Exam 1, you may not use anything other than –Your own brain and body –A single page (one side) of notes that you create•You can work with others to create your notes page4Lecture 10: NDPDAs/CFGs/PDAsMenu•Are DPDAs equivalent to NDPDAs?•Properties of CFLs•Equivalence of CFGs and NDPDAs5Lecture 10: NDPDAs/CFGs/PDAsLanguage ClassesRegular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsViolates Pumping LemmaFor CFLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwwwRwwWhere are DPDAs?6Lecture 10: NDPDAs/CFGs/PDAsProving Set EquivalenceA = B  A B and B  ASets A and B are equivalent if A is a subset of B and B is a subset of A.7Lecture 10: NDPDAs/CFGs/PDAsProving Formalism EquivalenceLR(M) = the set of languages that can be recognized by some M = { l | l  P(Σ*) and there is some m  M such that L(m) = l }A = B  LR(A) LR(B) and LR(B)  LR(A)8Lecture 10: NDPDAs/CFGs/PDAsProving Formalism Non-EquivalenceLR(M) = the set of languages that can be recognized by some M = { l | l  P(Σ*) and there is some m  M such that L(m) = l }A  B  There is an l  P(Σ*) that is in LR(A)but not in LR(B) or there is an l in LR(B) but not in LR(A)9Lecture 10: NDPDAs/CFGs/PDAsRegular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwwwRwwSensible option 1: LR(NDPDA)  LR(DPDA)  LR(NFA) = LR(DFA)Sensible option 2: LR(NDPDA) = LR(DPDA)  LR(NFA) = LR(DFA)To eliminate =, we need to find some language L that can be recognized by an NDPDA and prove it cannot be recognized by a DPDA10Lecture 10: NDPDAs/CFGs/PDAsLR(NDPDA)  LR(DPDA)A = { 0i1j | i  0, j = i or j = 2i }A  LR(NDPDA)ε, ε$0, ε+ε, εε1, +εε, $  εε, εε1, +ε1, εεε, $  ε11Lecture 10: NDPDAs/CFGs/PDAsLR(NDPDA)  LR(DPDA)A = { 0i1j | i  0, j = i or j = 2i }A  LR(DPDA)Proof by contradiction.Suppose there is a DPDA P that recognizes A.It must be in accept states only after processing 0i1i and 0i12i…0, αβ1, αβ2i transitions, consuming 0i1i…1, αβ1, αβi transitions, consuming 1i12Lecture 10: NDPDAs/CFGs/PDAsLR(NDPDA)  LR(DPDA)A = { 0i1j | i  0, j = i or j = 2i }A  LR(DPDA)Proof by contradiction.Suppose there is a DPDA P that recognizes A.It must be in accept states only after processing 0i1i and 0i12i…0, αβ1, αβ2i transitions, consuming 0i1i…1, αβ1, αβi transitions, consuming 2i22L(P’) = { 0i1i2i | i  0}13Lecture 10: NDPDAs/CFGs/PDAsLR(NDPDA)  LR(DPDA)A = { 0i1j | i  0, j = i or j = 2i }A  LR(DPDA)Proof by contradiction. If there is a DPDA P that recognizes A, we could construct a DPDA P' that recognizes A' = L(P') = { 0i1i2i | i  0} But, we know A' is not a CFL! (Prove using pumping lemma)So, there is no NDPDA that can recognize A', so there is no DPDA that can recognize A', so P' must not exist. Hence, P must not exist. This means there is no DPDA that can recognize A.14Lecture 10: NDPDAs/CFGs/PDAsRegular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwAwwLR(NDPDA)  LR(DPDA)  LR(NFA) = LR(DFA)Deterministic Context-Free Languages: recognized by DPDAA = { 0i1j | i  0, j = i or j = 2i }15Lecture 10: NDPDAs/CFGs/PDAsClosure 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 start A 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 that accepts if both accept16Lecture 10: NDPDAs/CFGs/PDAsClosure 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.17Lecture 10: NDPDAs/CFGs/PDAsCFLs 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 }18Lecture 10: NDPDAs/CFGs/PDAsCFLs 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  ε }19Lecture 10: NDPDAs/CFGs/PDAsClosure 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 ?20Lecture 10: NDPDAs/CFGs/PDAsCFLs 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.)21Lecture 10: NDPDAs/CFGs/PDAsClosure Properties of CFLsIf A and B are context free languages then: AR is a context-free language TRUEA* is a context-free language