This question is based on Turing machine and Computation Theory.

Problem 6:

Context-free grammars are sometimes used to model natural languages. In this problem you will model a fragment of the English language using context-free grammars. Consider the following English sentences: The girl is pretty. The girl that the boy likes is pretty. The girl that the boy that the clerk pushed likes is pretty. The girl that the boy that the clerk that the girl knows pushed likes is pretty. This is a special type of sentence built from a subject (The girl), a relative pronoun (that) followed by another sentence, a verb (is) and an adjective (pretty). (a) Give a context-free grammar G that models this special type of sentence. Your terminals should be words or sequences of words like pretty or the girl. (b) Is the language of G regular? If so, write a regular expression for it. If not, prove using the pumping lemma for regular languages. (c) Can you give an example of a sentence that is in G but does not make sense in common English