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

Question

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

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

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

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

Любая помощь приветствуется, большое спасибо!

Answer 1

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

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

Переводится как:

---

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

OR

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

---

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

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

Переводится как:

---

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

OR

Любое количество a с и b с, после любого числа a с

---

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

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

Переводится как:

---

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

---

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

(a U b)*

Та Да. Простой.

Answer 2

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

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

, что оставляет первую часть с:

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

Вкл.с правой стороны, у вас есть это

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

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

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

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

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

Я думаю, вот и все ...

Answer 3

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

Answer 4

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

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

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

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

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

Таким образом, единственное, что слева - это (a U b) *.

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

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

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

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