Michael Sipser Edition 3 Exercise 2 Question 32 (Page No. 157)

Question

Let $\Sigma = \{1, 2, 3, 4\}$ and  $C = \{w\in\Sigma^{*}\mid$ $\text{in }w,\text{ the number of }1\text{'s equals the number of }2\text{'s, and the number of } 3\text{'s equals the number of }4\text{'s}\}.$ Show that $C$ is not context free.

Answer 1

$L=\{w|w \in \{1,2,3,4\}^{*} \ where \ n_{1}(w)=n_{2}(w) \ and \ n_{3}(w)=n_{4}(w) \}$.

If $L$ is context-free then surely a PDA(NPDA or DPDA) acceptor exists and an equivalent generating CFG exists .

Let's imagine a PDA exists , and the behavior of the PDA  would be like :-

1. On seeing a 1 , if the top of the stack is 2 then pop stack and vice versa , else push 1 onto stack , and same is the case with 2's.

2. Same action as 1 will be done for 3 and 4 also.

3. And after reading the entire string , if the top of the stack is $Z_{0}$ then accept the string , else reject it.

Let us take a string here $w=1111333322224444$.
This $w\in L$ , but no PDA can accept such a string . Why? By the description of an informal machine given above , as soon as we see 2's we need to check top of the stack for 1's for matching , but by the time we reach 2's the top of the stack has 3's , thus matching is not possible using a single stack machine .

Thus , no PDA exists for the Language $L$
Moreover the Language $L1=\{1^{n}3^{m}2^{n}4^{m}|w \in \{1,2,3,4\}^{*} \ where \ n_{1}(w)=n_{2}(w) \ and \ n_{3}(w)=n_{4}(w) \} \subset L=\{w|w \in \{1,2,3,4\}^{*} \ where \ n_{1}(w)=n_{2}(w) \ and \ n_{3}(w)=n_{4}(w) \}$ and $L1$ is known to be non-context free , thus the superset cannot be context free.

Answer 2

Assume C is CFL

then CFL $\cap$ RL must CFL [closure property of intersection with regular language]

we know 1*2*3*4* is regular language

C $\cap$ {1*2*3*4*}=$1^n2^n3^n4^n$ which is not CFL

so C is not CFL