Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
I choose to Ogden pumping word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p &gt; n$.


I am afraid you could not show that Ogden's pumping lemma cannot be applied to $s$ since $s$ belongs to the context-free language, $P_1=\{a^{k}b^lc^md^n\mid k\not=l\wedge m\not=n\}$, which is a subset of $L^C$.

Although your approach does not work, your conclusion that $L^C$ isn't context-free is correct.



Well, you are quite near the right approach.

Let $P_2=L^C\cap L(a^*c^*b^*d^*)=\{a^{k}c^mb^ld^n\mid k\not=l\wedge m\not=n\}$. We can show word $a^{p}c^{p}b^{p+p!}d^{p + p!}$ cannot be pumped as described in Ogden's lemma for $P_2$ when all of its $a$'s are distinguished. Hence $P_2$ is not context-free. Since $L(a^*c^*b^*d^*)$ is regular, $L^C$ cannot be context-free.



Exercise 1. Show $P_1$ is context-free. Show $P_3$ is context-free, too where $P_3=\{a^{k}c^md^nb^l\mid k\not=l\wedge m\not=n\}$.

Exercise 2. Show $P_2$ is not context-free following the approach given above.

Exercise 3. Show the complement of the following language is not context-free, $\{ w : |w|_{a} = |w|_{b} \vee |w|_{c} \not= |w|_{d} \}$.