Упрощение регулярных выражений.

[Сомик]

Не подскажете, какую-нибудь прогу для упрощения регулярных выражений?
Я работаю с GAP, но там невозможно упростить выражение.
Например, GAP выдает (b((a + b)a)^*(a+b)b+a)^*(b((a+b)a)^*(a+b+\lambda)+\lambda), хотя это все лишь (a+b)^*

[powerZ]

Странные они у вас какие то, почему например круглые скобки вложенные?

[Сомик]

powerZ писал(а):

Странные они у вас какие то, почему например круглые скобки вложенные?

А что странного во вложенных скобках ?

[powerZ]

Так вроде круглые скобки означают адресацию в выражении, разве нет?

[Сомик]

powerZ писал(а):

Так вроде круглые скобки означают адресацию в выражении, разве нет?

Круглые скобки необходимы для того, чтобы поределит порядок выполнения операции. Например ((a+b)* с )* означает, что сначала получается язык состоящий из двух слов \{a,b\}, затем делаем его итрецию - получаем все слова в алфавите a,b, затем конкатинацию с буквой с. Получаем слова вида x_1 \dots x_s c, где x_j \in \{a,b\}. После чего итерация, получаем слова вида x_1 \dots x_s c \dots y_1 \dots y_k c, где x_j,y_i \in \{a,b\}.

[powerZ]

А вы уверены, что это тоже называется регулярными выражениями? Потому что я бы сказал например что (a+b)*c означает, что ищется последовательность из двух или более символов "a", оканчивающаяся символом "b", далее может быть любое количество произвольных символов, заканчивающихся символом c. Круглые скобки - для возможности адресации к первому фрагменту. Так что похоже ничем вам помочь не смогу

[незваный гость]

Существует много разных регулярных выражений. Есть традиция Unix'а (и С, Linux…), есть традиции математики (например, теории автоматов и матлогики несколько различаются).

[Сомик]

незваный гость писал(а):

есть традиции математики (например, теории автоматов и матлогики несколько различаются).

У меня как раз все с теорией автоматов связано.

[незваный гость]

Заметно.

[незваный гость]

Я не встречал таких программ. Для конечных автоматов известно, что задача распознования эквивалентности разрешима. Также разрешима задача минимизации автомата (ib idem).

Преобразование конечного автомата в удобочитаемое регулярное выражение — процесс более творческий. Более того, нет никакой гарантии, что р.в., автоматически построенное по минимальному автомату, окажется проще чем исходное.

В принципе, можно было бы попробовать написать такую программу — дурное дело нехитрое. Если писать на Python, всё получается очень буквально — как написано в определении, так и делаем. Думаю, работы на день–два.

Легко решаемая задача — проверка эквивалентности р.в.

Добавлено спустя 3 минуты 59 секунд:

Смешно и грустно — но больше всего времени уйдёт (до построеня р.в.) на разбор (чтение) р.в.

[luitzen]

Сомик,
есть такой проект — Forlan.

Скачайте минимальный набор инструментов и SMLNJ.
Установите SMLNJ и Forlan, как описано в инструкциях.

Запустив Forlan, Вы сможете иметь с ним диалоги наподобие следующего:

- Reg.toString(Reg.weakSimplify(Reg.fromString "b*(b+b%)+(%+%*)+(a+a)*a"));
val it = "% + aa* + bb*" : string
- Reg.toString(Reg.simplify Reg.weakSubset (Reg.fromString "b*(b+b%)+(%+%*)+(a+a)*a"));
val it = "a* + b*" : string
- fun Simplify s = Reg.toString(Reg.simplify Reg.weakSubset (Reg.fromString s));
val Simplify = fn : string -> string
- Simplify "% + aa* + bb*";
val it = "a* + b*" : string 

К сожалению, перед Вашим (b((a + b)a)*(a+b)b+a)*(b((a+b)a)*(a+b+%)+%) Forlan бессилен .