Question

Let $\mathbf{\sum }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{\#}\mathbf{\}}$. Let $\mathbf{C}\mathbf{=}\mathbf{\left\{}\mathbf{x}\mathbf{\#}{\mathbf{x}}^{\mathbf{R}}\mathbf{\#}\mathbf{x}\mathbf{|}\mathbf{x}\mathbf{\in }\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}\mathbf{*}\mathbf{\right\}}$ . Show that $\overline{\mathbf{C}}$ is a CFL.

Short answer

$\overline{\mathrm{C}}$ is a CFL.

Step-by-step solution

Explain CFL

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

Show that C¯ is a CFL.

Consider the given language $\mathrm{C}=\left\{\mathrm{x}\#{\mathrm{x}}^{\mathrm{R}}\#\mathrm{x}|\mathrm{x}\in \{0,1\}*\right\}$, that takes the input $\sum =\{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}\in \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}\in \mathrm{A}$, for all $\mathrm{m}\ge 0$.
2. $\left|\mathrm{bd}\right|>0$
3. $\left|\mathrm{bcd}\right|\le \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$\overline{\mathrm{C}}$is a Context-free Language.