91Ó°ÊÓ

Context Free grammars generate the context-free languages. The context-free languages are recognized by the automata.

Consider the given language $\mathrm{C}=\left\{\mathrm{x}\#{\mathrm{x}}^{\mathrm{R}}\#\mathrm{x}|\mathrm{x}∈\{0,1\}*\right\}$, that takes the input $∑=\{0,1,\#\}$.

To prove is that $\mathrm{C}$ is not a context-free language that implies that $\overline{\mathrm{C}}$ is a CFL.

Consider the string $\mathrm{k}=\mathrm{x}\#{\mathrm{x}}^{\mathrm{R}}\#\mathrm{x}∈\mathrm{C}$, contains $\left|\mathrm{x}\right|=\left|{\mathrm{x}}^{\mathrm{R}}\right|$ and $\left|\mathrm{k}\right|$ is a multiple of three. In contradiction, consider that the language $\mathrm{C}$ is a context-free language. For a context-free language, the pumping length $\mathrm{p}$. Consider the string $\mathrm{k}=0^{2\mathrm{p}}{0}^{\mathrm{p}}{1}^{\mathrm{p}}{0}^{2\mathrm{p}}$with $\left|\mathrm{k}\right|>\mathrm{p}$.The string $\mathrm{abcde}$ is a string that has,

1. ${\mathrm{ab}}^{\mathrm{m}}{\mathrm{cd}}^{\mathrm{m}}\mathrm{e}∈\mathrm{A}$, for all $\mathrm{m}â‰\yen 0$.
2. $\left|\mathrm{bd}\right|>0$
3. $\left|\mathrm{bcd}\right|≤\mathrm{p}$

Consider the following cases, that proves the contradictory.

Case 1: Since$\left|\mathrm{bd}\right|$ is not a multiple of three, ${\mathrm{k}}^{\text{'}}$is not a multiple of three where${\mathrm{k}}^{\text{'}}={\mathrm{ab}}^2{\mathrm{cd}}^2\mathrm{e}$

.

Case 2: $\left|\mathrm{bd}\right|=3\mathrm{q}$, that means it is the multiple of three. Then,

$\begin{array}{c}{\mathrm{ab}}^2{\mathrm{cd}}^2\mathrm{e}=0^{3\mathrm{p}+3\mathrm{q}}{1}^{\mathrm{p}}{0}^{2\mathrm{p}}\\ =0^{2\mathrm{p}+\mathrm{q}}{0}^{\mathrm{p}+2\mathrm{q}}{1}^{\mathrm{p}−\mathrm{q}}{0}^{2\mathrm{p}}\end{array}$

And it does not belongs to the language $\mathrm{C}$.

Case 3 : $\left|\mathrm{bd}\right|=3\mathrm{q}$ , that means it is the multiple of three, $\mathrm{bcd}$has only 1s. The resultant third string is ,

$\begin{array}{c}{\mathrm{ab}}^2{\mathrm{cd}}^2\mathrm{e}=0^{3\mathrm{p}}{1}^{\mathrm{p}+3\mathrm{q}}{0}^{2\mathrm{p}}\\ =0^{2\mathrm{p}+\mathrm{q}}{0}^{\mathrm{p}−\mathrm{q}}{1}^{\mathrm{p}+2\mathrm{q}}{1}^{\mathrm{q}}{0}^{2\mathrm{p}}\end{array}$

And it does not belongs to the language $\mathrm{C}$.

Since, the contradiction occurs at each case, thus the language $\mathrm{C}$is not a context-free language.

Therefore, it has been proved that the language$\stackrel{¯}{\mathrm{C}}$is a Context-free Language.