Поиск регулярных выражений для языков, описанных иначе - PullRequest
Новая
       5

Поиск регулярных выражений для языков, описанных иначе

2 голосов
/ 02 октября 2011

Позволяя {a b} быть набором алфавита, напишите регулярное выражение для:

1) Язык всех тех слов, в которых число a и число b оба нечетны;

2) Язык всех тех слов, длина которых нечетная и которые содержат подстроку ab.

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

1 Ответ

3 голосов
/ 02 октября 2011

Во-первых, есть простой DFA с 4 состояниями, который вы можете создать для распознавания языка. Затем вы можете использовать алгоритм, восстанавливаемый из теоремы Клини (часть, в которой он говорит, что все языки, распознаваемые FA, генерируются RE), чтобы получить RE, который работает ... или просто обосновать его на диаграмме.

Что касается второго, вы знаете, что (ab) является частью RE; Теперь вам нужно подумать обо всех уникальных способах, которыми вы можете добавить нечетное количество символов к этому (спереди или сзади), и соединить все эти возможности с + для простого и правильного RE.

Не думаю, что кому-то особенно нравится идея дать вам ответ.

EDIT:

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

Наш первый FA это: 

   Q s f(Q, s)
  -- - -------
  EE a     OE
  EE b     EO
  OE a     EE
  OE b     OO
  EO a     OO
  EO b     EE
  OO a     EO
  OO b     OE

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

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                     aa      EE
  EE                     ab      OO
  EE                      b      EO
  EO                      a      OO
  EO                      b      EE
  OO                      a      EO
  OO                     ba      EE
  OO                     bb      OO

Убедитесь, что это правильно, прежде чем продолжить. Далее мы избавляемся от ЭО: 

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                  aa+bb      EE
  EE                  ab+ba      OO
  OO                  ab+ba      EE
  OO                  aa+bb      OO

Чтобы упростить следующий шаг, мы вводим новый стартовый набор X и новое принимающее состояние Y; ОО больше не принимает. Мы исключаем необходимость в ОО: 

   Q                        regex f(Q, s)
  -- ---------------------------- -------
   X                        empty      EE
  EE aa+bb+(ab+ba)(aa+bb)*(ab+ba)      EE
  EE              (ab+ba)(aa+bb)*       Y

Таким образом, последнее регулярное выражение равно 

  (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*(ab+ba)(aa+bb)*

Мы можем начать пытаться перечислить наименьшие строки, которые это генерирует, просто как базовую проверку здравомыслия: {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, ...} Хорошо выглядит я!

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

...