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

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

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

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

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

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

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


dfa regular-language
person Community    schedule 04.11.2011    source источник
comment
Должен находиться на cstheory.stackexchange.com.   -  person orlp    schedule 05.11.2011
comment
@nightcracker: нет, не должно. Пожалуйста, ознакомьтесь с часто задаваемыми вопросами cstheory.   -  person Kaveh    schedule 05.11.2011
comment
Должно быть, вероятно, на Math.SE.   -  person Max    schedule 08.11.2011
comment
Кажется, вы намереваетесь d(s) быть значением s как двоичное число, не имеющее ничего общего с десятичным числом.   -  person Max    schedule 08.11.2011

Ответы (1)


arrow_upward
4
arrow_downward

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

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

Чтобы принимать числа, равные 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, но чтобы получить вашу нотацию, просто замените | на + и удалите $).

person Max    schedule 07.11.2011