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

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

и

b) Число, представленное w, делится на 3.

Написать регулярное выражениеДФА) для Л.

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('0123456789+') 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

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

Принимаем состояние 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)

Answer 3

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

(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.(потому что ввод не должен заканчиваться на плюс).