Этот язык регулярный? {0^n 1^m | m!= n}, я не понимаю прямого доказательства по длине накачки

Question

Этот язык регулярный? {0^n 1^m | m!= n}, я не понимаю прямого доказательства по длине накачки

Есть прямой способ доказать это: если p длина накачки, и мы берем строку s = 0^p1^p+p!тогда неважно что такое разложение s = xyz это строка xy^1+p!/|y|z будет равно 0^p+p!1^p+p! чего нет в языке.

Я не понимаю значение y, данное здесь.

0

regular-language automata pumping-lemma

Источник

user1714458 16 окт '14 в 02:12

1 ответ

Решение

Другие вопросы по тегам regular-language automata pumping-lemma

user405303 16 окт '14 в 02:30 2014-10-16 02:30 · Accepted Answer · 2014-10-16 02:30

y является некоторой подстрокой, которую можно "перекачивать" - повторять * раз - и при этом сохранять язык регулярным. По сути, мы должны найти где-то цикл, и этот цикл - то, что y представляет собой.

В основном, если язык имеет вид 0^m1^m! (m нули с последующим m! затем) там не может быть петли.

В этом случае, y представляет "гипотетическую строку насоса для языка подмножества {0^m1^m!}"- гипотетически, потому что он не может существовать! Ясно, что для этого меньшего языка прокачка невозможна, поскольку повторение немедленно выведет нас из языка. (рассмотрим пример 00111111 - Можем ли мы найти строку насоса для этого?) Таким образом, у нас есть особый случай языка, который не является регулярным, поэтому язык, как правило, не является регулярным. (хотя это, конечно, содержит особые случаи, которые являются регулярными, но это не оспаривается)