Насосная лемма в КПК и КЛЛ

Question

У меня вопрос про лемму прокачки, на котором я застрял ...

L = {w ∈ {a, b, c} ∗: na (w)

это КЛЛ или нет?

Я спрашиваю, что это не CFL, потому что недостаточно одного стека, чтобы запомнить все эти условия. Вы можете помнить, что na (w)

Или есть идеи для решения?

Answer 1

Обратите внимание, что для леммы Pumping требуется каждая строка в L , чтобы оставаться в L после перекачки.Таким образом, достаточно получить противоречие даже для какой-то конкретной формы строк в L .

a ^p b ^2p c ^3p - хороший пример, но я предлагаю попробовать более короткий: a ^p b ^{p + 1} c ^{p + 2} .

Обоснование почти такое же, как в статье в Википедии: Лемма прокачки: Использование ,У вас будут те же пять случаев, и в каждом из них довольно просто получить противоречие.