Алгебра регулярных событий. Доказательство тождеств.

[Killer]

Опять я с ещё одним вопросом из контрольной. "Докажите какие-либо тождества в алгебре регулярных событий". Видимо имеются ввиду тождества типа:

1. {{E}}={E}
2. {E}{E}={E}
3. E1 V E2 = E2 V E1 и т.д.
где E - множество слов содержащихся в Wx (Wx - множество всех слов в алфавите x)

Стыд и срам, но никак не могу найти материалов по этому поводу. Как это доказывается?

[DMVN]

Что-то мне кажется, что нечто подобное было у нас в лекциях по дискре в 7-м семестре (читали Лупанов и Угольников). Посмотрите вот тут:
http://dmvn.mexmat.net/logic.php?section=7 , вдруг поможет...

[Killer]

Вобщем-то да. Довольно хорошо рассказано о регулярных множествах, но вот про доказательство каких-нибудь тождеств не написано, к сожалению.

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

Ничего хитрого тут нет. Надо доказать, что всякое слово, удовлетворяющее левой части тождества, удовлетворяет правой, и наоборот. Иногда одно из вкдючений очевидно, например правое в левое в 1). Далее включение доказываются по индукции.

Иногда и индукция не нужна, в 3).

[Killer]

А я думал тут какая нибудь хитрость нужна, потому что алгебра регулярная, а не какая-нибудь там, обыкновенная. Продолжаю хит-парад глупых вопросов