Lecture 10: Exam 1 Context-Free Languages Contextually

2y ago
40 Views
2 Downloads
1.12 MB
5 Pages
Last View : 16d ago
Last Download : 6m ago
Upload by : Tia Newell
Transcription

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

Related Documents:

Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture

Past exam papers from June 2019 GRADE 8 1. Afrikaans P2 Exam and Memo 2. Afrikaans P3 Exam 3. Creative Arts - Drama Exam 4. Creative Arts - Visual Arts Exam 5. English P1 Exam 6. English P3 Exam 7. EMS P1 Exam and Memo 8. EMS P2 Exam and Memo 9. Life Orientation Exam 10. Math P1 Exam 11. Social Science P1 Exam and Memo 12.

GRADE 9 1. Afrikaans P2 Exam and Memo 2. Afrikaans P3 Exam 3. Creative Arts: Practical 4. Creative Arts: Theory 5. English P1 Exam 6. English P2 Exam 7. English P3 Exam 8. Geography Exam 9. Life Orientation Exam 10. MathP1 Exam 11. Math P2 Exam 12. Physical Science: Natural Science Exam 13. Social Science: History 14. Technology Theory Exam

Final Exam Answers just a click away ECO 372 Final Exam ECO 561 Final Exam FIN 571 Final Exam FIN 571 Connect Problems FIN 575 Final Exam LAW 421 Final Exam ACC 291 Final Exam . LDR 531 Final Exam MKT 571 Final Exam QNT 561 Final Exam OPS 571

Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued

Lecture 1: Introduction and Orientation. Lecture 2: Overview of Electronic Materials . Lecture 3: Free electron Fermi gas . Lecture 4: Energy bands . Lecture 5: Carrier Concentration in Semiconductors . Lecture 6: Shallow dopants and Deep -level traps . Lecture 7: Silicon Materials . Lecture 8: Oxidation. Lecture

TOEFL Listening Lecture 35 184 TOEFL Listening Lecture 36 189 TOEFL Listening Lecture 37 194 TOEFL Listening Lecture 38 199 TOEFL Listening Lecture 39 204 TOEFL Listening Lecture 40 209 TOEFL Listening Lecture 41 214 TOEFL Listening Lecture 42 219 TOEFL Listening Lecture 43 225 COPYRIGHT 2016

billionaire entrepreneur is an established phenomenon and China, for example, has created a significant share of the world’s self-made female billionaires. We believe that, like economic growth, great wealth creation has cycles. Wealth creation tends to move in S-curves, rather than growing linearly. At the end of the