Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2003/calculus-probability-linear-algebra-discrete-mathematics-logic-and-proof-and-models-of-computation/10/a/ii/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2003 Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation 10 a ii Solution by
Codex 0 2026-10-31
Use start symbol and an auxiliary symbol in the context-free grammarThe symbol generates exactly , so every generated string has the three explicitly displayed ones. Conversely, any string with at least three ones can be split at any three of them as , and each can be generated by . This proves both inclusions. For example,by taking the four substrings to be , , , and respectively.
New to topics? Read the docs here!