найти рег. Expr. более {0,1,2}, поэтому последний символ строки является суммой символов в строке mod 3. - PullRequest
Новая
       49

найти рег. Expr. более {0,1,2}, поэтому последний символ строки является суммой символов в строке mod 3.

0 голосов
/ 04 февраля 2012

Я самостоятельно изучаю формальные языки (Aho's, Hopcroft), но мне тяжело с регулярными выражениями.

Мне удавалось решать простые задачи, но эта поставила задачу, по крайней мере, для меня. Как решить эту проблему, если вы не можете считать до сих пор, я не привык к этому типу вычислений.
Должно быть какое-то свойство или что-то, что позволило бы мне обобщить ответ настолько, чтобы я мог выразить его как регулярное выражение.

До сих пор я придумал, что возможно, что будет как минимум 2 или 3 случая:

  • суммы mod3 = 0, если сумма = 3k
  • суммы mod3 = 1, если сумма = 3k + 1
  • суммы mod3 = 2, если сумма = 3k + 2.

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

Строка для отл. {122211}0 (фигурные скобки для удобства чтения) имеет ноль в конце, поскольку он удерживает это {sum=3k}0, если сумма равна "10" из строки для ex. {1222111}1 регистр может быть {sum=3k+1}, поэтому он должен быть в конце и так далее.

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

1 Ответ

0 голосов
/ 04 февраля 2012

Вот подсказка: подумайте о том, в каких разных конечных состояниях вы можете находиться. У вас, конечно, есть по крайней мере 3 состояния, поскольку количество значений может быть тремя разными вещами, в отличие от трех.Кроме того, вам нужно иметь отдельное начальное состояние, поскольку пустая строка не может быть принята.Вам нужно больше состояний?

Подсказка2: Я думаю, что вы можете легко сделать это с DFA, используя начальное состояние и девять других состояний, из которых будут приниматься ровно три.у вас есть DFA, вы можете использовать теорему Клини для построения эквивалентного регулярного выражения.Если вы предпочитаете регулярное выражение, вот еще один совет: если вы смотрите на любую строку длиной 3k, вы можете добавить: 0;любая строка длиной 1, за которой следует 1;любая строка длины 2, за которой следует 2. Таким образом, если вы можете написать регулярные выражения для строк длиной 3k, 1 и 2, вы практически закончили.

...