Регулярное выражение для строки цифр без повторных цифр?

Question

Я читаю через dragon book и пытаюсь решить упражнение, которое формулируется следующим образом

Написать регулярные определения для следующих языков:

• Всех строк цифр без каких-либо повторяющихся цифр. Подсказка: Попробуйте эту проблему сначала с помощью нескольких цифр, например {0, 1, 2}.

Несмотря на то, пытались решить в течение нескольких часов, я не могу представить себе решение, рядом с очень многословной

d0 -> 0? 
d1 -> 1? 
d2 -> 2? 
d3 -> 3? 
d4 -> 4? 
d5 -> 5? 
d6 -> 6? 
d7 -> 7? 
d8 -> 8? 
d9 -> 9? 
d10 -> d0d1d2d3d4d5d6d7d8d9 | d0d1d2d3d4d5d6d7d9d8 | ... 

Следовательно, чтобы писать 10! альтернативы в d10. Поскольку мы будем написать это регулярное определение, я сомневаюсь, что это правильное решение. Не могли бы вы мне помочь?

Answer 1

Так что вопрос не обязательно попросит вас написать регулярное выражение , он просил вас обеспечить регулярное определение, которое я истолковать включить НКА. Оказывается, не имеет значения, что вы используете, так как все NFA могут быть математически эквивалентны регулярным выражениям.

Используя цифру 0, 1, и 2, действительный НКА будет следующим (извините за вшивый диаграмме):

Каждого состояние представляет собой последнюю цифру сканированной на входе и на любом из узлов нет петель, поэтому это точное представление строки без повторных цифр из набора {0,1,2}. Расширение этого тривиально (хотя для этого требуется большая доска :)).

ПРИМЕЧАНИЕ. Я исхожу из предположения, что строка «0102» действительна, но строка «0012» - нет.

Это может быть преобразовано в регулярное выражение (хотя это будет болезненно) с использованием описанного алгоритма here.

Answer 2

(я не знаю, какой вариант регулярных выражений вы имеете в виду, если таковые имеются, таким образом, я буду предоставлять намеки на наиболее общем виде регулярных выражений.)

Я нахожу это довольно странное применение регулярные выражения, так как это точно один из тех случаев, когда они действительно не дают большого преимущества по сравнению с другими (более тривиальными для понимания) решениями.

Однако, если вы абсолютно хотите использовать регулярное выражение, вот подсказка (не решение, так как это упражнение, не дайте мне знать, если вам нужно больше подсказок):

Regex позволяет распознавать regular languages, которые являются обычно принимается deterministic finite state machines. Попробуйте найти конечный автомат, который принимает точно слова в указанном шаблоне. Это потребует состояния 2^10 = 1024, но не 10! = 3628800.

Answer 3

Я помню из своего курса теоретической информатики: если язык L является регулярным, то есть (не L), т.е. язык, содержащий все слова, не входящие в L. - Подходит ли это в контексте упражнение?

Answer 4

Вместо того, чтобы пытаться написать определение, которое определяет только то, что вы хотите, что если вы скажете ей, чтобы создать список всех строк до цифр до 10 цифр в длину, в том числе дублей, а затем вычитания в которые содержат два нуля, два ... и т. д.? Будет ли это работать?

Answer 5

Вот один из возможного строительства:

• Регулярное выражение для строки, которая содержит в лучшем случае один '0' цифра выглядит как (1-9) * (0 | эпсилон) (1-9) * - поэтому любое число 1-9 цифр, за которым следует ноль или 1 '0, за которым следует любое число 1-9 цифр.
• Теперь мы можем двигаться вперед, заметив, что если есть только одна цифра «1», она будет либо слева, либо справа от цифры «0» (или эпсилон, представляющий отсутствующую нулевую цифру). Таким образом, мы можем построить регулярное выражение, имеющее эти два случая или вместе взятые (|).
• Теперь мы можем рассверливать, говоря, что если есть только одна цифра «2», это может быть справа или слева от 1 цифры в двух возможных относительных местоположениях с цифрой «0».
• Итак, мы строим двоичное дерево, а количество регулярных выражений ORed составляет порядка 2^10, что является тем же самым порядком, что и FSM, принимающий этот язык. FSM для принятия языка должен иметь состояния (2^10 + 1), причем каждое состояние n можно рассматривать как двоичное представление n0n1n2n3n4n5n6n7n8n9, что означает n0 = увиденная цифра '0', n1 = увиденная цифра '1'. а повторная цифра переходит в одно не принимающее состояние. Начальное состояние равно нулю.

Если вам разрешено дополнять, то регулярное выражение, содержащее более одной цифры «0», будет (0-9) * 0 (0-9) * 0 (0-9) *, повторить для всех цифр, дополнять.

Вы можете определенно быть более компактным для интерпретации Питера Тейлора двух последовательных цифр, которые являются одинаковыми. Ясно, что состояние этой проблемы намного меньше.

SUCCINCTNESS OF THE COMPLEMENT AND INTERSECTION OF REGULAR EXPRESSIONS

«Исследование, проведенное в [2] показывает, что большинство из одного однозначного регулярного выражения, используемого на практике принимают очень простой вид:. Каждый символ алфавита происходит более одного раза Мы имеем в виду в качестве одноразовых регулярных выражений (SORE) и показать плотную экспоненциальную нижнюю границу для пересечения. "

...

«В этом разделе мы покажем, что при определении дополнение одного регулярное выражение, двойное экспоненциальное увеличение размера не может быть избежать вообще. В противоположность этому, когда выражение Однократное его дополнение может быть вычислено за полиномиальное время ».

Answer 6

Не знаете, что вы подразумеваете под "Регулярным выражением" в заголовке вопроса. Но если механизм регулярных выражений поддерживает отрицательный результат, это легко осуществить. (Вот PHP фрагмент)

$re = '/# Match string of digits having no repeated digits. 
    ^    # Anchor to start of string. 
    (?![^0]*0[^0]*0) # Assert 0 does not occur twice. 
    (?![^1]*1[^1]*1) # Assert 1 does not occur twice. 
    (?![^2]*2[^2]*2) # Assert 2 does not occur twice. 
    (?![^3]*3[^3]*3) # Assert 3 does not occur twice. 
    (?![^4]*4[^4]*4) # Assert 4 does not occur twice. 
    (?![^5]*5[^5]*5) # Assert 5 does not occur twice. 
    (?![^6]*6[^6]*6) # Assert 6 does not occur twice. 
    (?![^7]*7[^7]*7) # Assert 7 does not occur twice. 
    (?![^8]*8[^8]*8) # Assert 8 does not occur twice. 
    (?![^9]*9[^9]*9) # Assert 9 does not occur twice. 
    [0-9]+   # Match string of only digits. 
    $     # Anchor to end of string. 
    /x'; 

Answer 7

Регулярное определение представляет собой последовательность определений в виде

d1 -> r1

d2 -> r2

...

дп -> р-н

Теперь сделайте следующие определения:

Zero -> 0

One -> Zero (1 Zero) * | (Zero 1) + | 1 (ноль 1) * | (1 ноль) +

Два -> Один (2 Один) * | (Один 2) + | 2 (Один 2) * | (2 Один) +

Три -> Два (3 двух) * | (Два 3) + | 3 (Два 3) * | (3 два) +

Четыре -> Три (4 три) * | (Три 4) + | 4 (Три 4) * | (4 Три) +

...

Девять -> Восемь (9 Eight) * | (Восемь 9) + | 9 (Восемь 9) * | (9 Восемь) +

Answer 8

Я не думаю, что существует четкий способ написать регулярное выражение для решения этой проблемы без перечисления всех возможностей. Но я нахожу способ уменьшить сложность от O (N!) До O (2^N), определяя DFA следующим образом. В DFA, который я собираюсь построить, государство представляет, появилась ли какая-либо цифра или нет.

Возьмем строки, состоящие из {0, 1, 2}, например, 0 представляют '0', появился один раз, 0 'представляет' 0 'не появился. Все состояния будут выглядеть так: {012, 0'1'2 ', 0'12, 01'2, 012', 012 ', 01'2, 0'12}. Всего будет 2^3 = 8 состояний. И DFA выглядит следующим образом: DFA for strings with no repeating digits

Вы можете легко расширить его до {0,1,2, ..., 9}. Но будет 1024 государства. Тем не менее, я думаю, что это самый компактный DFA с интуитивным доказательством. По той причине, что каждое государство имеет уникальный смысл и не может быть объединено дальше.