Возможно ли упростить это регулярное выражение?

Я работаю на некоторых заданиях для моего класса компилятора и у меня есть следующая проблема:Возможно ли упростить это регулярное выражение?

Написать регулярное выражение для всех строк через х и б-х, которые содержат нечетное число a или нечетное число b (или оба).

После много досок работы я придумал следующее решение:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

однако, это наиболее упрощенная я могу получить его? Я подумал о том, чтобы построить DFA, пытаясь свести к минимуму количество состояний там, чтобы увидеть, облегчит ли это мне упрощение, но я решил, что сначала спрошу гуру-регекса на SO.

источник

2009-09-16 Anonymous

Какие дополнительные функции регулярного выражения вы можете использовать? –

он использует регулярные выражения в области компьютерных наук, а не PCRE или posix regex;) Они разные. –

@Brad Gilbert, я предполагаю, что нам разрешено использовать регулярное выражение, которое было введено до сих пор в книге, что мало. (*, +,?, |, [], ^). Довольно просто. – 2009-09-16 19:33:27

принять рекомендацию Greg двойки из начиная с (аа) *, и идти оттуда. Sepp2k почти прав, но реальное соображение состоит в том, что вы не заботитесь о другом письме. Я имею в виду, что когда вы смотрите на ограничение «нечетного числа», вам все равно, что такое b в вашей строке. Таким образом, палка б * S в любом месте вы можете :)

ответ Sepp2k является почти сразу, но это один является правильным:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

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

источник

2009-09-16 20:00:22

@Walt W, я управляю этим через свои шаги, но я думаю, что вы правы. – mmcdole

скажите мне регулярное выражение для любой строки, содержащей четное число a и четное число b? –

Вы имеете в виду четное число ИЛИ или четное число букв? Я полагаю, вы могли бы сделать И с нулевыми взглядами ... Это не стандартное средство регулярного выражения. Если вы хотите изменить это уравнение от нечетного до четного, просто отбросьте первые два члена каждого сегмента (b * a с левой стороны и a * b с правой стороны) –

Боюсь, что я не верю, что ваше регулярное выражение написано правильно. Рассмотрим строку:

aba

У нас есть пара вариантов для матчей, но тот факт, что это странно длины означает, что мы должны соответствовать одинокого А на фронте, так:

(a)(ba)

Но, к сожалению, , невозможно, чтобы ваша вторая основная группировка соответствовала (ba).

Когда я сталкивался с таким ограничением, мне было легче начать с основного ограничения и перейти оттуда. В этом случае ваше ограничение «странным», так начните с

a(aa)*

, чтобы заставить нечетное число a-х и идти оттуда. :)

источник

2009-09-16 19:38:42

@Greg D, это правда. Позвольте мне подумать об этом на секунду. – mmcdole

Это должно работать:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

источник

2009-09-16 19:50:44 sepp2k

Я писал что-то подобное :) Чтобы разработать, это регулярное выражение вычисляет все строки с нечетным числом (первый раздел), а OR - этими строками с любыми строками, содержащими нечетное число b. Однако здесь есть небольшая ошибка, так как в конце первого дня требуется b *, а второй - в конце. В противном случае аббба не будет приниматься. –

@ sepp2k, это работает во всех моих тестовых случаях. Можете ли вы описать свой мыслительный процесс, когда вы это делаете? Это намного проще, чем путь, по которому я спускался. – mmcdole

Никто не сказал, что он не может быть двусмысленным. Уолт прав, он еще не закончен, но все важные бит есть. :) –

Я думаю, вам нужно подойти к проблеме по-разному.

Вы пытаетесь сопоставить все, что не имеет даже чисел a и b.

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

источник

2009-09-16 20:10:17

Возможно ли упростить это регулярное выражение?

ответ

Смежные вопросы