Мы используем лемму прокачки для обычных языков, чтобы найти язык регулярный или нет.В домашнем задании есть вопрос, что я не знаю, как применить лемму накачки к языку.
L = {a$b: a,b ∈ {0,1}*, number of zeroes in a equals to the number of ones in b}
$ - это просто константа, чтобы разделить a и b.также язык такой, что:
L = {ab: a,b ∈ {0,1}*, number of zeroes in a equals to the number of ones in b}
Я понимаю, что теперь нет ничего, чтобы разделить a и b, и невозможно сделать предположения о количестве нулей в a и количестве единиц в b, верно?Или я ошибаюсь?
Как применить накачку к этим языкам, чтобы доказать их правильность или нет?