1David Evanshttp://www.cs.virginia.edu/evanscs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 11: Lecture 11: ParsimoniousParsimoniousParsingParsing2Lecture 11: Parsimonious ParsingMenu• Fix proof from last class• Interpretive Dance!• Parsimonious Parsing (Parsimoniously)PS3 Comments Available TodayPS3 will be returned Tuesday3Lecture 11: Parsimonious ParsingClosure Properties of CFLsIf A and B are context freelanguages then:ARis 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 ?4Lecture 11: Parsimonious ParsingComplementing Non-CFLsLww= {ww | w ∈Σ* } is not a CFL. Is its complement?Yes. This CFG recognizes is: S → 0S0 | 1S1 | 0X1 | 1X0X → 0X0 | 1X1 | 0X1 | 1X0 | 0 | 1 | εBogus Proof!S → 0X1 → 01X01 → 0101 ∈∈∈∈ LwwWhat isthe actual language?5Lecture 11: Parsimonious ParsingCFG for Lww(L¬ww)S → SOdd| SEvenAll odd length strings are in L¬wwSOdd→ 0R | 1R | 0 | 1R → 0SOdd| 1SOddSEven→ XY | YXX → ZXZ | 0Y → ZYZ | 1Z → 0 | 1How can we prove this is correct?6Lecture 11: Parsimonious ParsingSoddgenerates all odd-length stringsSOdd→ 0R | 1R | 0 | 1R → 0SOdd| 1SOddProof by induction on the length of the string.Basis. SOddgenerates all odd-length strings of length 1. There are two possible strings: 0 and 1. They are produces from the 3rdand 4thrules.Induction. Assume SOddgenerates all odd-length strings of length n for n = 2k+1, k ≥ 0. Show it can generate all odd-length string of length n+2.27Lecture 11: Parsimonious ParsingSOddgenerates all odd-length stringsSOdd→ 0R | 1R | 0 | 1R → 0SOdd| 1SOddInduction. Assume SOddgenerates all odd-length strings of length n for n = 2k+1, k ≥ 0. Show it can generate all odd-length string of length n+2.All n+2 length strings are of the form abt where t is an n-length string and a ∈ {0, 1}, b ∈ {0, 1}. There is some derivation from SOdd⇒* t (by the induction hypothesis). We can generate all four possibilities for a and b:00t: SOdd→ 0R → 00SOdd ⇒* 00t01t: SOdd→ 0R → 01SOdd ⇒* 01t10t: SOdd→ 1R → 10SOdd ⇒* 10t11t: SOdd→ 1R → 11SOdd ⇒* 01t8Lecture 11: Parsimonious ParsingCFG for Lww(L¬ww)S → SOdd| SEvenSOdd→ 0R | 1R | 0 | 1R → 0SOdd| 1SOddSEven→ XY | YXX → ZXZ | 0Y → ZYZ | 1Z → 0 | 1?Proof-by-leaving-as-“Challenge Problem” (note: you cannot use this proof technique in your answers)9Lecture 11: Parsimonious ParsingEven StringsShow SEvengenerates the set of all even-length strings that are not in Lww.Proof by induction on the length of the string.Basis. SEvengenerates all even-length strings of length 0 that are not in Lww. The only length 0 string is ε. ε is in Lwwsince ε = εε, so ε should not be generated by SEven. Since SEvendoes not contain any right sides that go to ε, this is correct.SEven→ XY | YXX → ZXZ | 0Y → ZYZ | 1Z → 0 | 110Lecture 11: Parsimonious ParsingClosure Properties of CFLsIf A and B are context freelanguages then:ARis a context-free language TRUEA*is a context-free language TRUEA is not necessarily a context-free language (complement)A ∪ B is a context-free language TRUEA ∩ B is a context-free language ?Left for you to solve (possibly on Exam 1)11Lecture 11: Parsimonious ParsingWhere is English?Regular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsViolates Pumping LemmaFor CFLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwAwwDeterministic CFLs12Lecture 11: Parsimonious ParsingEnglish ∉ Regular LanguagesThe cat likes fish.The cat the dog chased likes fish.The cat the dog the rat bit chased likes fish.…This is a pumping lemma proof!313Lecture 11: Parsimonious ParsingChomsky’s Answer (Syntactic Structures, 1957)= DFA= CFG14Lecture 11: Parsimonious ParsingCurrent Answer• Most linguists argue that most natural languages are not context-free• But, it is hard to really answer this question:e.g., “The cat the dog the rat bit chased likes fish.” ∈ English?15Lecture 11: Parsimonious ParsingWhere is Java?Regular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsViolates Pumping LemmaFor CFLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwAwwDeterministic CFLs16Lecture 11: Parsimonious ParsingInterpretive Dance17Lecture 11: Parsimonious ParsingWhere is Java?Regular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsViolates Pumping LemmaFor CFLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwAwwDeterministic CFLs18Lecture 11: Parsimonious ParsingWhat is the Java Language?public class Test {public static void main(String [] a) {println("Hello World!");}}Test.java:3: cannot resolve symbolsymbol : method println (java.lang.String)// C:\users\luser\Test.javapublic class Test {public static void main(String [] a) {println ("Hello Universe!");}} }Test.java:1: illegal unicode escape// C:\users\luser\Test.javaIn the Java LanguageNot in the Java Language419Lecture 11: Parsimonious Parsing// C:\users\luser\Test.javapublic class Test {public static void main(String [] a) {println ("Hello Universe!");}} }> javac Test.javaTest.java:1: illegal unicode escape// C:\users\luser\Test.java^Test.java:6: 'class' or 'interface' expected} }^Test.java:7: 'class' or 'interface' expected^Test.java:4: cannot resolve symbolsymbol : method println (java.lang.String)location: class Testprintln ("Hello World");^4 errorsParsing errorsScanning errorStatic semantic errors20Lecture 11: Parsimonious ParsingDefining the Java Language{ w | w can be generated by the CFG for Java in the Java LanguageSpecification }{ w | a correct Java compiler can builda parse tree for w }21Lecture 11: Parsimonious ParsingParsingS → S + M | MM → M * T | TT → (S) | number3 + 2 * 1SSM+M T*1T2MT3DerivationParsingProgramming languagesare (should be) designed to make parsing easy, efficient, and unambiguous.22Lecture 11: Parsimonious ParsingUnambiguousS → S + S | S * S | (S) | number3 + 2 * 1SSS+S*123S3 + 2 * 1SSS*1SS+3223Lecture 11: Parsimonious ParsingAmbiguityHow can one determine if a CFG is ambiguous?Super-duper-challenge problem: create a program that solve the “is this CFG ambiguous” problem:Input: CFGOutput: “Yes” (ambiguous)/“No” (unambiguous) Warning: Undecidable Problem Alert!(Not only can you not do this, it is impossible for any program to do this.)(We will