Использование свойств закрытия для доказательства регулярности - PullRequest
Новая
       8

Использование свойств закрытия для доказательства регулярности

1 голос
/ 27 февраля 2011

Вот домашнее задание: 

Is L_4 Regular?
Let L_4 = L*, where L={0^i1^i | i>=1}.

Я знаю, что L нерегулярно, и я знаю, что Kleene Star является закрытой операцией, поэтому я предполагаю, что L_4 нерегулярно.

Однако мой профессор привел пример вышеизложенного, в котором L = {0^p | p is prime}, который он сказал, был регулярным, доказав, что L* равен L(000* + e), сказав, что каждый был подмножеством друг друга (e в данном случае означает пустое слово).

Таким образом, его метод включал формирование регулярного выражения 0^p, но как я могу это сделать, когда у меня его уже есть?

1 Ответ

1 голос
/ 28 февраля 2011

Обычные языки закрыты под звездой Клини. То есть, если язык R регулярен, то и R *.

Но рассуждения не работают в другом направлении: существуют нерегулярные языки P, для которых P * фактически является регулярным.

Вы упомянули один такой P в своем вопросе: множество строк 0 ^ p, где p простое число.

Легко использовать насосные леммы для обычных и контекстно-свободных языков, чтобы показать, что P по крайней мере контекстно-зависимый. Однако P * эквивалентен языку 0 ^ q, где q - сумма нулей или более простых чисел. Но это верно для q = 0 (пустая строка) и любого q> = 2, поэтому P * можно распознать с помощью DFA с 3 состояниями, даже если сам P не является регулярным.

Таким образом, L, не зависящий от контекста, не имеет никакого отношения к тому, является ли ваш L_4 = L * регулярным или нет. Если вы можете создать DFA, который распознает L_4, как я сделал для P * выше, то, очевидно, это регулярно. В процессе поиска DFA, который работает, вы, вероятно, увидите некоторую закономерность появляются, которые могут быть использованы в качестве основы для накачки аргумента. Теорема Майхилла-Нероде является еще одним подходом к доказательству нерегулярности языка и полезна, если язык поддается анализу префиксов и различающихся расширений. Если язык можно разложить на конечный набор классов эквивалентности при определенном отношении, то его можно распознать с помощью DFA, содержащего такое много состояний.

...