Problem $10$

Consider the following context$-$free grammar $($CFG$)$ G$,$ with start symbol S:

$SAB|BC$

$Aa|$

$Bb$

$Cc|$

Convert the given CFG G into Chomsky Normal Form $($CNF$).$ Provide the

resulting grammar with all necessary productions. Explain how you applied the

CNF conversion rules. Show how the string $"a{b}^p$ can be derived using the CNF

grammar, if possible.

Problem $11$

Suppose we have a grammar G with n productions, none of them $-$productions,

and convert this grammar to CNF$.$ Show that the CNF grammar has at most

$O(n^2)$ productions.

Problem $12$

Design a context$-$free language $L$ such that any string in $L$ consists of a balanced

combination of parentheses, square brackets, and curly braces. Then, demon$-$

strate how to apply the Pumping Lemma for Context$-$Free Languages to prowe

that $L$ is indeed context$-$free. Additionally, provide an explanation of how the

Pumping Lemma could be used to show that a language containing strings of

the form $\{a^n{b}^n{c}^n|n0\}$ is not context$-$free.

Problem $13$

Design a Turing decider $M$ that accepts the language $L$ defined as follows:

is a binary string representing a number divisible by $3$