Является ли язык L = {s ∈ (0 + 1) * |d (s) mod 5 = 2 и d (s) mod 7! = 4} регулярно?

Question

Во время чтения из книги у меня было это сомнение.

Упоминается, что

L = {s ∈ (0 + 1) * | n0 (s) mod 7 = n1 (s) mod5 = 0} является регулярным Где n0 (s) = число 0 в с и n1 (s) = количество 1 в с

Далее упоминается, что

L = {s ∈ (0 + 1) * | d (s) mod 5 = 2 и d (s) mod 7! = 4} не являются регулярными (даже не контекстно-зависимыми, но рекурсивными) Где d (s) = десятичное значение s (например, d (101) = 5)

Почему это так? Это потому, что DFA не имеет памяти для хранения (запоминания) десятичного значения s? Но в таком случае почему первый язык считается регулярным?

Answer 1

В вашем учебнике либо есть ошибка, либо вы неправильно ее читаете: второй язык, который вы называете обычным:

DFA может вычислить значение двоичного числа (или любого базового числа) по модулю m (для любого m ).Просто m состояний пронумерованы от 0 до m -1;читая ноль, переходите из текущего состояния с в ( с * 2) мод м ;при чтении перейдите к ( с * 2 + 1) мод м .Чтобы увидеть, что это работает, нужно только посмотреть, как работает бинарный файл, и что ( a + b ) мод m = ( a мод м + б мод м ) мод м (и аналогично для умножения).

Принятьчисла, равные k mod m , делают k принимающим состоянием;чтобы принять числа, отличные от k mod m , сделайте все остальные состояния приемлемыми.Это означает, что {s ∈ {0,1} * |d (s) mod 5 = 2} и {s ∈ {0,1} * |d (s) mod 7! = 4} - оба обычных языка.Язык L является их пересечением, а обычные языки закрыты на пересечении, поэтому L является регулярным.

Язык {s ∈ {0,1} *|d (s) mod 5 = 2} принимается регулярным выражением '(((0 * 10 (10 * 10) * 10 * 11 | 0 * 11) ((00 | 1) (10 * 10) * 10 *11 | 01) * (00 | 1) (10 * 10) * 0 | 0 * 10 (10 * 10) * 0) (0 ((00 | 1) (10 * 10) * 10 * 11 | 01) *(00 | 1) (10 * 10) * 0 | 1) * 0 ((00 | 1) (10 * 10) * 10 * 11 | 01) * (00 | 1) (10 * 10) * | (0* 10 (10 * 10) * 10 * 11 | 0 * 11) ((00 | 1) (10 * 10) * 10 * 11 | 01) * (00 | 1) (10 * 10) * | 0 * 10(10 * 10) *) $ '(здесь я использовал нотацию Python, но для получения нотации просто замените | на + и удалите $).