Как Kleene Star взаимодействует с оператором Union?

Question

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

Я понимаю идею, что (& эпсилон; U аа *) = {& эпсилон;} U {а, аа, ааа, ...} = а *

Однако, я не смог найти ни одного подтверждение того, что (& epsilon; U a *) = a *.

Кроме того, если у меня есть выражение (U a *), не было бы оно эквивалентно *?

Последние два заявления «кажутся», очевидно, истинными для меня, но я подозрительный, потому что лекционные заметки по всей сети, похоже, не позволяют сделать эти связи, и мой учебник (Sipser) не упоминает ни одного из Это.

Answer 1

Да (ε U a *) = a * истинно.

Вы можете подтвердить это равенством, которое вы дали, и tautology x U x = x.

Начать с (ε U а *) = (Е U (е U аа *)) = (е U е) U аа * = ε U аа * = а *

Аналогично (а U а *) = (a U (ε U aa *)) = (ε U (a U aa *)), то коэффициент = (ε U a (ε U a *)) = (ε U aa *) = a *