Доказательство того, что язык не является регулярным, с помощью леммы о накачке

Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму о накачке.

L = {ak b3l al | к 1 , л 0}

Я решил выбрать w = a b3p ap, тогда |w| = 4п+1п

Какие-нибудь советы?

Спасибо!


person Aln    schedule 21.06.2016    source источник


Ответы (1)


Я не уверен в точной формулировке леммы о накачке, которую вы используете. В любом случае, это довольно сложный случай, потому что стандартные формулировки вроде википедии позволяют прокачать только где-то в префиксе фиксированной длины. Но ваш начальный блок позволяет прокачиваться где угодно и может быть сколь угодно длинным. Таким образом, вы должны использовать некоторое дополнительное свойство. Я предлагаю два:

  • Обычные языки закрыты при обращении. Таким образом, вы также можете посмотреть на $L^R = {a^l b^{3l} a^k}$. Теперь любая прокачка в начальном блоке приведет к выходу из языка.
  • Регулярные языки закрыты при пересечении. Если вы возьмете пересечение с b+ a+, вы получите ${a b^{3l} a^k}$, и теперь прокачка блока b выведет вас из языка.
person Peter Leupold    schedule 22.06.2016
comment
Я изменил строку w в соответствии с вашим предложением. Затем я могу взять x = пустую строку, y = a и z остальное, и все готово. - person Aln; 22.06.2016