0
$\begingroup$

$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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\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
    Commented Feb 11, 2019 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$
    – John L.
    Commented Feb 11, 2019 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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