$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} \}$.

  • $\begingroup$ 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!) ? $\endgroup$ – PoliteMan Feb 11 at 4:08
  • $\begingroup$ 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$. $\endgroup$ – Apass.Jack Feb 11 at 5:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.