Построить КПК для дополнения

Мне интересно, возможно ли это вообще, так как . Поэтому КПК, который может отличить слово от остальной части вполне может принять его , что звучит противоречиво для меня. w ∈ { a n b n c n ∣ n ≥ 0 } { a ∗ b ∗ c ∗$\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$$w\in\{a^n b^n c^n \mid n \geq 0\}$$\{a^*b^*c^*\}$

Думаю, мне нужно воспользоваться недетерминированным характером КПК, но у меня нет идей. Если бы вы могли дать совет, я был бы очень признателен.

Нет, это не зависит от контекста. Чтобы принять , вам нужно убедиться, что три числа равны. Чтобы принять a ∗ b ∗ c ∗ ∖ a n b n c n , вам просто нужно убедиться, что вы находитесь в одном из следующих трех случаев:$a^nb^nc^n$$a^*b^*c^* \setminus a^nb^nc^n$

1. Число s отличается от числа b s; или$a$$b$
2. Число s отличается от числа c s; или$a$$c$
3. Число s отличается от числа c s.$b$$c$

Запишите КПК для каждого из этих случаев, затем объедините их, недетерминированно перейдя к каждому из начального состояния.