Головоломка с регулярным выражением

Question

Это не домашнее задание, а старое экзаменационное задание. Мне любопытно увидеть ответ.

Нам дан алфавит S = {0,1,2,3,4,5,6,7,8,9, +}. Определите язык L как набор строк w из этого алфавита так, что w находится в L, если:

a) w - это число, такое как 42 или w - (конечная) сумма чисел, таких как 34 + 16 или 34 + 2 + 10

и

б) число, представленное ш делится на 3.

Написать регулярное выражение (и DFA) для L.

Answer 1

Это должно работать:

 
^(?:0|(?:(?:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\ 
+)*[369]0*)*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?: 
\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[ 
258](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0 
\+)*[147])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+)(?:\+(?:0|(?:(? 
:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?:\+?(?:0\+)* 
[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[258](?:0*(? 
:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])* 
(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+) 
*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+))*$ 

Он работает, имея три состояния, представляющие сумму цифр до сих пор по модулю 3.Он запрещает ведущие нули по номерам и плюс знаки в начале и конце строки, а также два последовательных знака плюс.

Генерация регулярных выражений и испытательного стенда:

a = r'0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*' 
b = r'a[147]' 
c = r'a[258]' 

r1 = '[369]|[147](?:bc)*(?:c|bb)|[258](?:cb)*(?:b|cc)' 
r2 = '(?:0|(?:(?:' + r1 + ')0*)+)' 
r3 = '^' + r2 + r'(?:\+' + r2 + ')*$' 
r = r3.replace('b', b).replace('c', c).replace('a', a) 

print r 

# Test on 10000 examples. 

import random, re 
random.seed(1) 
r = re.compile(r) 
for _ in range(10000): 
    x = ''.join(random.choice('') for j in range(random.randint(1,50))) 
    if re.search(r'(?:\+|^)(?:\+|0[0-9])|\+$', x): 
     valid = False 
    else: 
     valid = eval(x) % 3 == 0 
    result = re.match(r, x) is not None 
    if result != valid: 
     print 'Failed for ' + x 

Answer 2

Не полное решение, просто идея:

(B): Знаки «плюс» здесь не имеют значения. abc + def таких же, как abcdef ради делимости на 3. В последнем случае, есть регулярное выражение здесь: http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-to-determine-if-a-base-10-number-is-divisible-by-3

совместить это с требованием (A), мы можем принять решение (B) и изменить это:

• Первый символ чтения должен быть 0..9 (не плюс)

• Вход не должен заканчиваться знаком плюс, так: Дублируйте каждое состояние (будет использовать S для исходного состояния и S' для дублирования, чтобы различать их). Если мы находимся в состоянии S, и мы читаем плюс, мы перейдем к S'.

• При чтении номера мы перейдем в новое состояние, как если бы мы были в S. S' государства не могут принять (другой) плюс.

• Кроме того, S' не является «принимающим государством», даже если S есть. (потому что вход не должен заканчиваться плюсом).

Answer 3

Обратите внимание, что моя память о синтаксисе DFA сильно устарела, поэтому мой ответ, несомненно, немного сломан. Надеюсь, это даст вам общее представление. Я решил полностью игнорировать +. Поскольку состояния AmirW, abc + def и abcdef одинаковы для целей делимости.

Accept состояние является C.

A=1,4,7,BB,AC,CA 
B=2,5,8,AA,BC,CB 
C=0,3,6,9,AB,BA,CC 

Обратите внимание, что выше язык использует все 9 возможных спариваний ABC. Он всегда будет заканчиваться либо A, B, либо C, и тот факт, что каждое использование переменной является парным, означает, что каждая итерация обработки сокращает строку переменных.

Пример:

1490 = AACC = BCC = BC = B (Fail) 
1491 = AACA = BCA = BA = C (Success)