Question

Let B be the language of all palindromes over {0,1} containing equal numbers of 0s and 1s. Show that B is not context free.

Short answer

B={ $\overline{)\mathrm{w}}\mathrm{w}\in \left\{0,1\right\}*,\mathrm{w}={\mathrm{w}}^{\mathrm{R}}$and w contains equal number 0s of and 1s}

This language is not context free this can be proof by using pumping lemma.

Step-by-step solution

Step 1:

Let B be the language of all palindromes over {0,1} which contains equal numbers of 0s and 1s.

Palindrome is a sequence of digits or anything that are same if we read from starting and ending.

For example {radar, refer, wow, noon}

Here the language given us is containing equal no of 0s and 1s so there the language of palindrome is as follows

B= {001100, 011110, 10011001, 110010011}

Here the pumping lemma is used to find the language is context free or not.

pumping lemma for CFG is defined as,

1. Assume B is CFG and there L is 0s and 1s. where Z is belongs to L.

$$\begin{gathered} \left|z\right|\ge n \\ z=uvwxy \\ \left|v\right|\ge 1 \end{gathered}$$

Here atleast 1 is not null.

1. Find a suitable k so that$u{v}^{k}w{x}^{k}y\notin L$so L is not context free language.

$$\begin{gathered} L=\left\{a^n{b}^n\overline{)c^n}n\ge 0\right\} \\ z=uvwxy, \\ z=a^n{b}^n\overline{)c^n}\left\{n=1,z=abc\right\} \\ \left|z\right|=3n>n \end{gathered}$$

If we equate both z then we get,

$$\begin{gathered} uvwxy=a^n{b}^n{c}^n \\ \left|vx\right|\ge 1,\left\{n\ge \left|vx\right|\ge 1\right\} \end{gathered}$$

Then after that,

Let v or x is a part of -

$$\begin{gathered} \left(a^j{b}^j\right)or\left(b^i{c}^j\right) \\ v=\left(a^j{b}^j\right) \\ {v}^2=\left(a^j{b}^j\right)\left(b^i{c}^j\right) \\ u{v}^{2}w{x}^{2}y=a^m{b}^m{c}^m \end{gathered}$$

From there, it is proof that

$u{v}^{2}w{x}^{2}y\notin L$

Therefore, L is not context free language.

Proving for Language B by Pumping Lemma

For proving the given question let v or x is a part of $\left(1^i{1}^j\right)$

Then,

$$\begin{gathered} v=\left(1^i{1}^j\right) \\ {v}^2=\left(1^i{1}^j\right)\left(1^i{1}^j\right) \\ u{v}^{2}w{x}^{2}y=\left(1^i{1}^j\right) \end{gathered}$$

So, there it shows,

$u{v}^{2}w{x}^{2}y\notin B$

Therefore, the given language in B is not context free language.

Determine the L is not context free language by another method

(c)

Here the language B is not context free language this statement is also correct by this, It states that if any language contain two conditions which is must then we can say this language is not context free language.

And in the given question the two important conditions are

1. The Language B is a palindrome.
2. It contains equal number of 0s or 1s.

Therefore,the given language in B is not context free language.