7.5. Понятие о регулярных выражениях алгебры событий.

Поведение автомата можно было бы описать, поставив каждой входной последовательности однозначно в соответствие выходную последовательность. Но в общем случае это невозможно сделать, из-за бесконечного множества этих входных последовательностей. Выход был найден – использование конечных формул для представления бесконечного множества последовательностей. Эти конечные формулы получили название – «регулярные выражения».

Последовательность входных сигналов будем называть входным словом. Любое множество входных слов назовем событием. Множество входных слов Si, которое вызывает появление на выходе автомата сигнал bi. Назовем событием, представленном в автомате М выходным сигналом bi. Разработана специальная алгебра – алгебра событий. В этой алгебре используются три операции: дизъюнкция, произведение и итерация событий и задаются некоторые законы (правила ТИФ)

Пример:

Элементарное событие – любое множество, состоящее из одного слова или из пустого слова е. Любое событие, представимое конечной формулой алгебры событий, символы элементарных событий, называемое регулярным событием, а сама такая формула – регулярным выражением.

Теорема Клини. Любое регулярное выражение представимо в конечном автомате.

Для задания автомата, имеющего выходной алфавит B=(b1, b2…bi) достаточно разбить множество входных слов на i события S1, S2,… Si, представленных соответственно выходным сигналам b1, b2,.. bi. Поэтому соответственно можно определить реакцию автомата на любое входное слово.

Некоторые примеры представленные регулярным выражением событий во входном алфавите А={a1, a2…. ai}

1)События, содержащие все однобуквенные и только однобуквенные слова алфавита А

S1=a1 a2 …. ai

2)События, состоящие из всех двухбуквенных слов алфавита А

S2=( a1 a2 …. ai)( a1 a2 …. ai)

3)События, состоящие из всех слов алфавита А

S3= { a1 a2 …. ai }

В алфавите (x, y, z) =A регулярное выражение

4) S4=x{xyz}(yz)

задает регулярное событие, состоящее из всех слов, которые начинаются буквой x и заканчиваются буквой y или z .

А={x1, x2}

5)описать автомат, выдающий сигнал w1, всякий раз, когда происходит изменение входной буквы с x1на x2, т.е. сигнал w1 должен выдаваться в ответ на любые последовательности, кончающиеся буквами x1 x2

S5={ x1x2}x1x2