Question 1 (12 marks). In class we saw how to encode graphs to use them with Turing machines, in the tutorial we discussed how to encode DFAs. You are to describe an encoding scheme for context-free grammars as outlined below.

A) Describe a scheme that encodes any context-free grammar, using the definition of context-free grammars provided in class.

B) Use an example to illustrate your coding scheme in A).

C) Describe, using an implementation-level Turing machine description, how a Turing machine can verify whether or not its tape content corresponds to the encoding of a well-defined context-free grammar, as specified in your encoding scheme in A).