Операции в алгебре событий
Алгебра событий включает три операции:
· Дизъюнкцию (объединение) событий;
· Произведение событий;
· Итерацию событий.
Дизъюнкцией событий S1, S2, …, Sk называют событие S = S1vS2v…vSk, состоящее из всех слов, входящих в события S1, S2, …, Sk.
Пример. Событие S1 содержит слова x1, x2x1, x1x1,т.е. S1 = (x1, x2x1, x1x1), а S2 = (x2, x1x2). Тогда S = S1vS2 = (x1, x2, x1x1, x1x2, x2x1).
Произведением событий S1, S2, …, Sk называется событие S = S1* S2* …,*Sk, состоящее из всех слов , полученных приписыванием к каждому слову события S1 каждого слова события S2, затем слова события S3 и т.д.
Пример. S1и S2 те же. S = S1*S2 = (x1x2, x1x1x2, x2x1x2, x2x1x1x2, x1x1x2, x1x1x1x2). Произведение событий не коммутативно, т.е. слова, входящие в события S1S2 и S2S1 различны: т.е. S1S2№S2S1 . Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий S1S2 можно сказать, что событие S2 умножено на событие S1справа, а событие S1на S2 слева.
Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными.
Итерацией события S называется событие{S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности. Т.е. {S} = e v S v SS v SSS v….
Пример. S = (x2, x1x2).
{S} = (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …)
При синтезе конечных автоматов важнейшую роль играют регулярные события. Пусть дан конечный алфавит X = (x1, x2, …, xm).
Определение. Любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операции дизъюнкции, произведения и итерации, называется регулярным событием, а выражение, составленное с помощью этих операций – регулярным выражением.
предыдущая темаследующая