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

Question

Как вы можете доказать, что приведенный ниже язык L не является контекстно-независимым, я хотел бы знать, имеет ли смысл приведенное ниже доказательство, если нет, то какой будет правильный метод доказательства?

L = {a ^ nb ^ nc ^ i | n ≤ i ≤ 2n}

Я пытаюсь решить этот язык противоречием.Предположим, что L регулярно и с длиной накачки p такой, что S = a ^ pb ^ pc ^ p.Заметьте, что S ∉ L. Так как должен быть цикл накачки xy с длиной меньше p, это может дублировать y, состоящее из некоторого числа b, чтобы заставить x (y ^ 2) z войти в язык, потому что число b превышаетчисло c больше не ограничено данным условием i, которое равно n ≤ i ≥ 2n, поэтому мы имеем противоречие и, следовательно, язык L не является контекстно-свободным.

Answer 1

Доказательство от противного.Предположим, что язык не зависит от контекста.Тогда, по накачанной лемме для контекстно-свободных языков, любая строка в L может быть записана как uvxyz, где | vxy |

0 и для всех натуральных чисел k, u (v ^ k) x (y ^ k) z также есть в языке.Выберите ^ pb ^ pc ^ (p + 1).Тогда мы должны быть в состоянии написать эту строку как uvxyz, чтобы | vy |> 0. Есть несколько возможностей для рассмотрения:

1. v и y состоят только из а.В этом случае накачка в любом направлении приводит к различию чисел a и b, что приводит к появлению строки не на языке;так что это не может иметь место.
2. v и y состоят только из a и b.В этом случае перекачка может сохранить числа a и b одинаковыми, но подкачка со временем приведет к тому, что число c будет меньше числа a и b;так что это не может иметь место.
3. v и y состоят только из b.Этот случай аналогичен (1) выше и поэтому не может быть правильным выбором.
4. v и y состоят только из b и c.Также аналогично (1) и (3) в том, что накачка приведет к тому, что числа a и b будут различаться.
5. v и y состоят только из c.Накачка в конечном итоге приведет к тому, что число с будет больше, чем в два раза;так что это не может быть так.

Независимо от того, как мы выберем v и y, подкачка будет производить строки не на языке.Это противоречие;это означает, что наше предположение о том, что язык не зависит от контекста, должно быть неверным.