Учитывая, что L = {w принадлежит {a, b} * | w имеет много а как б}
докажите, что L не является регулярным
Мои рассуждения:
решение проблемы требует леммы прокачки для обычных языков.
Таким образом, множество L состоит из таких элементов, как: L = {ab, aabb, aaabbb, aaaabbbb .....}
Лемма прокачки говорит, что если L регулярно, то есть постоянная n такая, что w
принадлежность к L есть> = n, и w можно разложить на три части xyz.
Также необходимо учитывать следующие правила:
1.y не является пустой строкой (y является средней частью w)
2 |. XZ | <= n </p>
3. для каждого k> = 0 тогда xy ^ kz должен все еще принадлежать L
Если мы установим k = 0, тогда правило 3. становится xz, которое, конечно, не принадлежит L
так как число а не равно числу б.
Я на самом деле предположил, что, поскольку у - средняя часть строки, у нее в основном больше а, чем б
поэтому xz не соответствует строковым требованиям для того, чтобы быть элементом L.
В двух словах L не является регулярным
Я прав? Что-то не так с моим подходом к решению проблемы?
Заранее спасибо.
Joachim