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

Ответ 1

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

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

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

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

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

Ответ 2

Здесь одна возможная конструкция:

• Регулярное выражение для строки, содержащей не более одной цифры "0", выглядит как (1-9) * (0 | epsilon) (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) *, повторите для всех цифр, дополнение.

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

УСПЕХНОСТЬ ДОПОЛНЕНИЯ И ПЕРЕСЕЧЕНИЯ РЕГУЛЯРНЫЕ ЭКСПРЕССИИ

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

...

"В этом разделе показано, что при определении дополнения к единому регулярное выражение, увеличение двухэкспоненциального размера не может быть вообще избегали. Напротив, когда выражение одно-однозначное его дополнение может быть вычислено в полиномиальное время".

Ответ 3

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

Ответ 4

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

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

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

Regex позволяет вам распознавать обычные языки, которые обычно принимаются детерминированные машины с конечным состоянием. Попробуйте найти конечный автомат, который принимает точно слова в указанном шаблоне. Для этого потребуются состояния 2^10 = 1024, но не 10! = 3628800.

Ответ 5

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

d1 → r1

d2 → r2

...

dn → rn

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

Zero → 0

Один → Нулевой (1 ноль) * | (Zero 1) + | 1 (ноль 1) * | (1 ноль) +

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

Три → Два (3 Два) * | (Два 3) + | 3 (Два 3) * | (3 Два) +

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

...

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

Ответ 6

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

Ответ 7

Не уверен, что вы подразумеваете под "Регулярным выражением" в заголовке вопроса. Но если механизм регулярных выражений поддерживает отрицательный результат, это легко осуществить. (Здесь фрагмент 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';

Ответ 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 для строк без повторяющихся цифр

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