Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму о накачке.
L = {ak b3l al | к 1 , л 0}
Я решил выбрать w = a b3p ap, тогда |w| = 4п+1п
Какие-нибудь советы?
Спасибо!
Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму о накачке.
L = {ak b3l al | к 1 , л 0}
Я решил выбрать w = a b3p ap, тогда |w| = 4п+1п
Какие-нибудь советы?
Спасибо!
Я не уверен в точной формулировке леммы о накачке, которую вы используете. В любом случае, это довольно сложный случай, потому что стандартные формулировки вроде википедии позволяют прокачать только где-то в префиксе фиксированной длины. Но ваш начальный блок позволяет прокачиваться где угодно и может быть сколь угодно длинным. Таким образом, вы должны использовать некоторое дополнительное свойство. Я предлагаю два: