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

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

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


regular-language automata pumping-lemma automata-theory
person Saul    schedule 17.03.2020    source источник
comment
Привет и добро пожаловать в Stack Overflow. Этот сайт работает лучше всего, когда вы даете людям работу, которую вы пробовали до сих пор, чтобы они могли помочь вам с конкретными частями вашего решения. С леммой о накачке у вас возникли проблемы с поиском накачивающей струны? Или у вас возникли проблемы с доказательством того, что ваша строка всегда может быть перекачана в слово вне языка для любой декомпозиции? Я бы предложил накачать строку a^n c b^(n+1), где n произвольно велико, как того требует лемма накачки.   -  person Welbog    schedule 17.03.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

person Patrick87    schedule 17.03.2020