Как я могу доказать, что этот язык является регулярным?

Question

Я пытаюсь доказать, если этот язык:

L = {w = {0,1} * | #₀(w)% 3 = 0} (число 0 делится на 3)

регулярно пользуется леммой прокачки, но я не могу найти способ сделать это. Все остальные примеры, которые я получил, имеют простую форму или, скажем, более определенную форму, такую ​​как w = a^x b^y c^z и т. Д.

Answer 1

Любая строка на этом языке, содержащая не менее трех символов, имеет это свойство: либо строка имеет " 1"в нем или их три" 0 подряд.

Если строка содержит 1 , затем вы можете разделить его, как в лемме прокачки и установить у, равный некоторому 1 в строке. Тогда очевидно, что строки xyz, xyyz, xyyyz и т. Д. Находятся в языке, потому что все эти строки имеют одинаковое количество нулей.

Если строка не содержит 1 , он содержит три 0 подряд. Установка Y для этих трех 0 s, должно быть очевидно, что xyz, xyyz, xyyyz и т. д. все в языке, потому что вы добавляете три 0 символы каждый раз, так что у вас всегда есть ряд 0 делится на 3.

@justhalf в комментариях совершенно правильно; Лемму накачки можно использовать для доказательства того, что можно качать обычный язык или что язык, который нельзя накачать, не является регулярным, но вы не можете использовать лемму накачки, чтобы доказать, что язык в первую очередь является регулярным. Моя вина.

Вместо этого, вот доказательство того, что данный язык является регулярным на основе теоремы Майхилла-Нерода:

Рассмотрим множество всех строк 0 с и 1 s. Разделите эти строки на три набора:

E ₀, все строки такие, что число 0 s кратно трем,

E ₁, все строки такие, что число 0 s больше, чем кратно трем,

Е ₂, все строки такие, что количество 0 s на два больше, чем кратно трем.

Очевидно, что каждая строка 0 с и 1 s находится в одном из этих трех наборов.

Кроме того, если x и z обе строки 0 с и 1 s, то рассмотрим, что это значит, если конкатенация xz находится в L:

1. Если x находится в E ₀, то xz находится в L тогда и только тогда, когда z находится в E ₀

2. Если x находится в E ₁, то xz находится в L тогда и только тогда, когда z находится в E ₂

3. Если x находится в E ₂, то xz находится в L тогда и только тогда, когда z находится в E ₁

Следовательно, на языке теоремы нет различающего расширения для любых двух строк в одном из наших трех наборов E _i, и, следовательно, существует не более трех классов эквивалентности. Конечное число классов эквивалентности означает, что язык регулярен.

(на самом деле, существует ровно три класса эквивалентности, но это не нужно)

Answer 2

Я не думаю, что вы можете использовать насосную лемму, чтобы доказать, что язык является регулярным. Чтобы доказать, что язык является регулярным, вам просто нужно дать регулярное выражение или DFA. В этом случае регулярное выражение довольно просто:

1 * (01 * 01 * 01 *) *

(доказательство: регулярное выражение явно не принимает ни одну строку, у которой число 0 не делится на 3, поэтому нам просто нужно доказать, что все возможные строки, у которых число 0 делится на 3, принимаются этим регулярным выражением, которое это можно сделать, подтвердив, что для строк, содержащих 3n 0, регулярное выражение соответствует ему, поскольку 1^n₀01^n₁01^n₂01^n₃... 01^n_3n-201^n_3n-101^n_3n имеет то же самое число 0 и n_k можно заменить так, чтобы оно совпадало со строкой и чтобы этот формат был четко принят регулярным выражением)

Насосная лемма не может быть использована для доказательства правильности языка, потому что мы не можем установить y как в ответе Даниэля Мартина. Вот контрпример в том же формате, что и его ответ (пожалуйста, исправьте меня, если я делаю что-то принципиально отличное от его ответа):

Докажем, что язык L = {w = 0ⁿ1^p | n ∈ N, n> 0, p простое число} регулярно с использованием леммы прокачки следующим образом: обратите внимание, что есть хотя бы одно вхождение 0, поэтому мы принимаем y в качестве 0 и имеем xy^k z = 0^{n + k- 1}1^р, которые все еще удовлетворяют определению языка. Следовательно, L регулярно.

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

Answer 3

• Язык является регулярным тогда и только тогда, когда его распознает какой-то недетерминированный конечный автомат.
• Автомат - это конечный автомат.

Мы должны построить автомат, который восстанавливает L.
Для каждого государства мыслить так:

• "Где я?"
• "Куда я могу пойти, с какой-то данной записью?"

Итак, для L = { w={0,1}* | #0(w) % 3 = 0 }
Возможные варианты (состояния): Остаток (остаток от деления) равен 0, 1 или 2. Это означает, что нам нужно три состояния. Пусть q0, q1 и q2 - состояния, представляющие оставшиеся деления 0,1 и 2 соответственно.

q0 - начальное и конечное состояние.
Теперь для записей "0" выполните математику # 0 (w)% 3 и перейдите в соответствующее состояние.
Переходные функции:
f (q0, 0) = q1
f (q1, 0) = q2
f (q2, 0) = q0

Для записей "1" он просто зацикливается, где бы он ни находился, потому что он не меняет состояние машины.
f (qx, 1) = qx

Лемма прокачки доказывает, что какой-то язык не является регулярным.
Вот хорошая книга по теории вычислений: Введение в теорию вычислений, 3-е издание, Майкл Сипсер.