Как прокачать лемму для обычного языка

Question

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

Показать, что L = { a^n c b^m | n, m are natural numbers and n < m} не является регулярным.

Answer 1

Выберите ^ p c b ^ 2p. Эта строка на языке, так как p <2p. Накачка любой непустой подстроки в первых p символах этой строки более чем в p раз гарантированно приведет к увеличению числа a за пределы числа b. Это противоречит утверждению прокачивающей леммы о том, что выполнение этого для строки на обычном языке должно дать другую строку на этом языке. Таким образом, язык не может быть регулярным. </p>