# Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

$$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$$

In my opinion complement of the L language is

$$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$$

I choose to Ogden pummping lemma word $$s = a^{p}b^{p + p!}c^{p}d^{p + p!}$$ and $$p > n$$

I would like to distinguish $$c ^ {p}$$. And then I have to have at least one distinguished symbol and the rest not distinguished and in my opinion it can't be pumped in any case because i can $$c^{p}$$ pumped to $$c^{p + p!}$$ so it isn't context-free

Do I think right?

I choose to Ogden pumping word $$s = a^{p}b^{p + p!}c^{p}d^{p + p!}$$ and $$p > 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} \}$$.

• Exercise 3. L^C = |w|_a != |w|_b ^ |w|_c = |w|_d have i right? We can choose word a^pc^pb^(p+p!)d^(p+p!) ? – PoliteMan Feb 11 '19 at 4:08
• It looks like you made a typo since $a^pc^pb^{p+p!}d^{p+p!} \not\in L^C$, which cannot be used to disprove context-freeness. You probably meant $a^pc^pb^{p+p!}d^p$. – John L. Feb 11 '19 at 5:51