Накачка леммы в контекстно-свободных языках

Question

A = {0^a 1^b 2^c | a < b < c}

Мне нужно показать, что A не является контекстно-свободным. Я предполагаю, что для этого мне нужно использовать Лемму прокачки, но как?

Answer 1

Цель состоит в том, чтобы доказать, что для любой струны с длиной> = минимальной длины накачки, строка не может быть накачана. То есть, если вы разделите его на подстроки uvxyz, строка, полученная в результате создания копий (или удаления копий) v и y, все еще будет на языке A.

Обратите внимание, что вам нужно только показать, что одна строка на языке не может быть перекачена (при условии, что она соответствует минимальной длине перекачки p)

Рассмотрим этот язык и как он относится к A:

Answer 2

Шаг первый: определите минимальную длину прокачки (2 ^ p + 1), где p - количество переменных. Шаг второй: сделайте несколько строк такой длины. Шаг третий: начните разрезать строки в vwxyz так, чтобы | wy ​​|> 0 (заметьте, что | x | CAN может быть нулем) и | wxy | <= 2 ^ p + 1. Посмотрите, как можно определить w и y, а также то, что происходит, когда вы начинаете повторять эти подстроки на месте. </p>

Ключ, вероятно, будет находиться на разделительной линии между 0 и 1.