Как следует доказать (или найти), являются ли два регулярных выражения одинаковыми или эквивалентными?

Question

Например, в заданном мне задании нас попросили выяснить, равны ли два регулярных выражения или нет.

(a+b+c)*  and ((ab)**c*)*

Мой вопрос: как это сделать?Если я нарисую графики переходов для обоих, а затем проведу через них несколько строк и покажу, что оба TG способны принять его, является ли это достаточным доказательством?Если нет, как мне это сделать?Есть ли математический / аксиоматический подход к этому?

Заранее спасибо.

РЕДАКТИРОВАТЬ: Есть еще одна вещь, которую я хотел бы прояснить, которая имеет отношение к этому вопросу.Являются ли две FA, изображенные на фотографии ниже, одинаковыми?

т.е. одинаковы ли значения (1) и (2) на изображении выше?

Answer 1

Существует алгоритм, чтобы определить, равны ли они:

1. Построить NFA-лямбды, соответствующие каждому RE, используя теорему Клини
2. Создайте DFA для каждого, используя конструкцию подмножества / powerset
3. (необязательно) Минимизируйте DFA, используя стандартный алгоритм минимизации DFA.
4. Построение DFA для L (M1) \ L (M2) и L (M2) \ L (M1) с использованием декартовой конструкции машинного изделия
5. (Необязательно) Минимизируйте эти цены за тысячу показов.
6. Определите, принимает ли каждая строка какие-либо строки, проверяя все строки в алфавите E размером не более | Q | (работает из-за леммы прокачки для обычных языков)

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

РЕДАКТИРОВАТЬ: Да, эти DFA одинаковы. Первое - это просто сокращенное обозначение второго.

Answer 2

Два регулярных выражения R и T эквивалентны, если язык, определенный R (т. Е. Набор строк, сгенерированный регулярным выражением R), равен языку, определенному T. Чтобы доказать эквивалентность для регулярных выражений, мыиспользуйте доказательства сдерживания из теории множеств.То есть, если S1 - это набор строк, сгенерированных регулярным выражением R, а S2 - набор строк, сгенерированных регулярным выражением T, мы должны доказать, что S1 ⊆ S2 и S2 ⊆ S1.Оба направления необходимы для доказательства равенства множеств.

- Из лекций CSc 4340 GSU Fall 09 (Dr. Raj Sunderraman)

Answer 3

Предполагая

1. Для иллюстрации вставлены пробелы
2. ( ( a b )* * c* )* на самом деле ((ab)*c*)**,
3. Каждый шаблон заключен в ^ и $.

Эти регулярные выражения НЕ совпадают.

abccabcc не будет соответствовать (a+b+c)*, но будет соответствовать ((ab)*c*)*

Как я нашел это?

Когда я внимательно посмотрел на эти шаблоны, я обнаружил 2 вещи.

1. Первый принимает более 1 а и б {1,}. Таким образом, всегда будет последовательность a и последовательность b рядом. как aaaabb, aabbbbb и т. д. Но во втором шаблоне a и be будут соседствовать с одним экземпляром. как ab, ababab, abababab и т. д.
2. c появится только 1 раз после последовательности a и последовательности b. Но во втором паттерне с может появляться столько раз, сколько может.

Answer 4

((ab) ^^ c ^) ^ = (a ^ b ^ c ^) ^ = (a + b + c) ^

Answer 5

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

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

Answer 6

Они разные, что легко определить по квантификаторам.Чтобы первое выражение соответствовало чему-либо, оно должно содержать c.Второй, очевидно, может обойтись без c.(Есть еще много различий, но это должно помочь вам начать).