Как я могу доказать, что этот язык не является контекстно-свободным?

У меня есть следующий язык

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

Я пытаюсь определить, к какому классу языка Хомского он подходит. Я могу видеть, как это можно сделать, используя контекстно-зависимую грамматику, поэтому я знаю, что это, по крайней мере, контекстно-зависимо. Кажется, что это не было бы возможно сделать с контекстно-свободной грамматикой, но у меня есть проблема, доказывающая это.

Кажется, что лемма прокачки проходит потому, что если помещен в третью часть любого слова (раздел со всеми с). Он может качать и столько раз, сколько вы хотите, и он останется на языке. Если я ошибаюсь, не могли бы вы сказать мне, почему, если я прав, я все еще думаю, что этот язык не является контекстно-свободным, так как я могу доказать это?2 V $uvwxy$$2$$v$$x$

Вы можете заставить накачку быть в некоторых местах, используя лемму Огдена , например, отмечая все 0.

Предположим, что он не содержит контекста, тогда лемма Огдена дает вам , вы даете ему который есть в языке, и вы «помечаете» все 0. Тогда любая факторизация должна быть такой , что существует в или . Вы также можете принять и поскольку и должны быть подстроками вашего языка.w = 0 p 1 p 2 p w = u x y z v 0 x z x = a k z = b m x x z $p>0$$w=0^p1^p2^p$$w=uxyzv$$0$$x$$z$$x=a^k$$z=b^m$$xx$$zz$

1. Если то имеет больше 0, чем 1w = u x 2 y z 2$z=0...0$$w=ux^2yz^2v$

2. Если и то имеет больше 1, чем 2.z = 1..1 w = u x 2 y z 2$x=0..0$$z=1..1$$w=ux^2yz^2v$

3. Если и то имеет больше 0, чем 1.z = 2..2 w = u x 2 y z 2$x=0..0$$z=2..2$$w=ux^2yz^2v$

Так что - это не слово вашего языка. Следовательно, он не является контекстно-свободным.$ux^2yz^2v$

Для других методов, см. Обсуждение: Как доказать, что язык не является контекстно-свободным?

Насосная лемма следует решить вашу проблему в отношении третьей части слова; обратите внимание , что , когда вы разделяете , любая комбинация также на языке, в том числе при . Попробуй это.у V п ш х п у п = $z = uvwxy$$uv^nwx^ny$$n = 0$

РЕДАКТИРОВАТЬ: Как утверждает jmad , Лемма прокачки похожа на игру:

1. Лемма прокачки дает вам$p$
2. Вы даете слово языка длиной не менее$s$$p$
3. Насосная лемма переписывает это так: с некоторыми условиями ( и )| V X Y | ≤ p | V y | ≥ $s=uvxyz$$|vxy|≤p$$|vy|≥1$
4. Вы даете целое число$n≥0$
5. Если не в , вы выиграли, не является контекстно-свободным.L $uv^nxy^nz$$L$$L$

Итак, вам нужно указать слово, разбить 3 на случаи и показать, что для каждого случая вы можете найти так, чтобы полученное слово отсутствовало в языке.$n$

Когда вы разделяете , подумайте обо всех случаях, в которые может попасть . Вы заметите, что если не попадает в 2, то легко прокачивать 0 и 1, пока они не превосходят 2, и тогда у вас есть слово, которого нет в языке. Мое предложение состоит в том, что, если попадает на 2 территории, вы также можете заставить и исчезнуть, установив , поэтому . Затем, исключив 2, вы можете получить слово, которое не входит в язык.v x y v x y v x y v y n = 0 u v n x y n z = u x $s=uvxyz$$vxy$$vxy$$vxy$$v$$y$$n=0$$uv^nxy^nz = uxz$