Насосная лемма для обычного языка: можем ли мы изменить первое условие на "для каждого i > 0"?

Насосная лемма из < Введение_в_в_счете_компьютера >"

Вопрос: Можем ли мы изменить первое условие на for each i > 0 вместо for each i ≥ 0?

1 ответ

Да, вы можете сделать это, однако это сделает лемму о прокачке менее полезной. Мы используем лемму о накачке, чтобы сказать, что грамматика не является регулярной, и она даже не обязательно работает для всех нерегулярных языков. Небольшое ограничение ее применимости хорошо, но не нужно, тем более что метод доказательства подразумевает, что вы можете накачать подстроку. так и вверх.

Другие вопросы по тегам