Упростить это регулярное выражение

Я занимаюсь некоторыми упражнениями перед экзаменом для моего класса компиляторов и должен упростить это регулярное выражение.Упростить это регулярное выражение

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Совершенно очевидно, что e - это пустая строка, а U обозначает объединение.

До сих пор, я думаю, что один из (a U b) * можно удалить, как объединение U a = a. Однако я не могу найти никаких других упрощений, и я не очень хорошо справляюсь с другими проблемами до сих пор. :(

Любая помощь приветствуется, спасибо очень много!

источник

2011-02-10 CompilersBeginner

Я бы очень хотел объяснять любые ответы или даже подсказки, а не ответы, я делаю упражнения перед экзаменом, ответы без объяснений мне не помогут! Благодаря! – CompilersBeginner

Я верю, что мой принятый ответ неверен, как указано в комментариях. Я действительно думаю, что результат действительно (U b) *, но мое объяснение неверно. – Piva

немного ржавый на регулярное выражение, но если * еще представляет «ноль или более вхождений» вы можете заменить:

(a U e)b* for (a U b)*

, который покидает первую часть с:

(a U b)*(a U b)* = (a U b)*

С правой стороны, у вас есть, что

(b U e)a* = (b U a)*

Теперь, так как U б = б U а, вы получите:

(a U b)*(a U b)*

на правой стороне, которая оставляет только

(a U b)* U (a U b)* = (a U b)*

Я думаю, что это ...

источник

2011-02-10 01:59:58 Piva

О, боже мой, у меня болит голова, поскольку мое регулярное выражение тоже ржавое. Вы можете быть правы, но * что случилось с токеном 'e' *? Я не вижу, как это устраняется. Но возможно, что я этого не вижу (опять же, возраст и недостаток кофе в сочетании с ржавкой регулярного выражения). –

Первый шаг неправильный, поскольку предыдущий разрешает только 1 'a' и только в первой позиции. –

@BoltClock: В ответе, который я вижу, нет 'a?'. –

Я думаю, что все, что эквивалентно (a U b)* (или в большинстве регулярных выражений грамматик, (a|b)*)

источник

2011-02-10 01:56:01

Поскольку я занимаюсь практическими проблемами для экзамена, меня гораздо больше интересует, как вы пришли к такому выводу. Не могли бы вы поделиться этим? – CompilersBeginner

Вот мои рассуждения: посмотрите на левую ветвь верхнего союза. Сначала возьмите '(a U b) * (a U e)'; распределите конкатенацию через объединение, чтобы получить '(a U b) * a U (a U b) *'. Вторая часть представляет собой надмножество первого, что сворачивается в '(a U b) *'. Добавление 'b *' в конец делает то же самое: все, что соответствует '(a U b) * b *', также будет соответствовать '(a U b) *' и наоборот. Это делает RE в '(a U b) * U (a U b) * (b U e) a *'; поскольку правая сторона может принимать только строки 'a' и' b', это подмножество левой стороны, поэтому RE упрощает просто '(a U b) *'. –

@CompilersBeginner: Две формы эквивалентны, если соответствие первого означает совпадение второго, а совпадение второго означает совпадение первого, правильно? Ваше выражение никогда не вводит никаких токенов, кроме 'a' и' b', поэтому все, что соответствует ему, также соответствует '(a U b) *'. И любой '(a U b) *' соответствует вашему, беря первую ветвь '(a U b) * (a U e) b *', а затем выбирая ветвь с пустой строкой '(a U b) * eb * 'и, наконец, выбор числа повторений 0 для' b * '. –

Первый тран Сланец на английский описание языка:

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Переводит к:

Любая последовательность a с или b с последующим дополнительным a, за которым следует любое количество b сек ,

ИЛИ

Любое количество a с и b с последующим дополнительным b, follwed любым количеством a s

Существует много совпадений здесь - по крайней мере (a U b)*(a U e) является точно так же, как (a U b)*, потому что «Любая последовательность a s и b s« обязательно либо заканчивается a, либо epsilon (as любая строка может заканчиваться эпсилон), так что эти группы могут быть устранены, в результате чего

(a U b)*b* U (a U b)*a*

Переводит на:

Любая последовательность a с или b с последующим любым количеством b сек ,

ИЛИ

Любое количество a с и b с, follwed любым количеством a с

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

(a U b)*(a* U b*)

Переводит на:

Любая последовательность a с или b с последующим любым количеством a с или любым числом b с.

теперь держат на минуту, «Любая последовательность As и Bs» обязательно заканчивается «Любая последовательность a с или любой последовательности b с», что означает, что все, что соответствует первой части может соответствовать все регулярное выражение (потому что вторая часть может иметь нулевую длину), так почему бы нам не сделать это

(a U b)*

Ta Da. Просто.

источник

2011-02-10 02:01:18 tobyodavies

По вашим рассуждениям (a U b) * b будет уменьшаться одинаково ... но это не так. Вы должны убедиться, что все совпадения продолжают совпадать, но все отклоненные входы все еще отклоняются, и ваш аргумент пропустил последнее. –

@Ben Какой шаг теряет информацию? Многие упрощения полагаются на все конечные биты, которые могут иметь длину 0, что не соответствует вашему примеру, поэтому я не уверен, что вы имеете в виду. – tobyodavies

@Ben, i_think_ вы ссылаетесь на мои 1-й или 3-й шаги, когда я говорю, что, поскольку 1-е повторение _ обязательно должно заканчиваться вторым, мы можем удалить второе, что опять не применимо к вашему примеру - '(a U b)' не обязано заканчиваться буквой 'b' - это может закончиться' a', поэтому упрощение не применяется. – tobyodavies

я дам вам представление о том, как я бы решить: (не очень формальный и нет никакой гарантии)

Посмотрите на левой стороне главного U:

(а U б) * - Что это значит? Комбинация a's и b's длины n, где n> = 0.

Далее идет (U U). Что же мы имеем здесь? A или пустое слово. Если бы мы хотели этого, мы могли бы просто получить его в предыдущей части. Если мы хотим e, мы все равно можем его оставить. Обратите внимание на то, что нам не нужно брать a, потому что у нас есть возможность выбрать e. Поэтому мы можем пропустить всю эту часть.

Что дальше? б *. Что это? Как и многие б, как мы хотим. Мы могли бы получить их и в первой части! мы можем оставить это!

Итак, единственное, что слева (U b) *.

Давайте посмотрим на правой стороне:

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

Мы также получим (a U b) * таким же образом.

Итак, в конце мы имеем (a U b) * U (a U b) *, который, как вы знаете, равен (a U b) *.

источник

2011-02-10 02:06:31 FabianB

По вашим рассуждениям '(a U b) * b' будет уменьшаться одинаково ... но это не так. –

Спасибо за подсказку, я пытался дать менее формальный подход в своем ответе. Я не уверен, как улучшить ответ, не сказав этого. – FabianB

Упростить это регулярное выражение

ответ

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