МПС
Операции в алгебре событий (Тема)Алгебра
событий включает три операции: 1)
Дизъюнкцию (объединение) событий; 2)
Произведение событий; 3)
Итерацию событий. Дизъюнкцией
событий 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). Определение. Любое событие, которое
можно получить из букв данного алфавита с помощью конечного числа операции
дизъюнкции, произведения и итерации, называется регулярным событием, а
выражение, составленное с помощью этих операций – регулярным выражением. Очевидно любое событие, состоящее из
конечного множества слов, является регулярным. Действительно, такие события
можно представить в виде дизъюнкции всех входящих в него слов, образованных из
букв заданного алфавита с помощью операции умножения. События, состоящие из
бесконечного числа слов, могут быть как регулярными, так и не регулярными. Теорема. Любые регулярные выражения и
только они представимы в конечных автоматах. Из этой теоремы следует, что
любой алгоритм преобразования информации, который можно записать в виде
регулярного выражения, реализуется конечным автоматом. С другой стороны, любые
конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в
виде регулярных выражений. Рассмотрим,
как можно совершить переход от описательной формы задания алгоритмов работы
конечных автоматов к представлению этих алгоритмов в виде регулярных выражений.
С целью упрощения такого перехода вводят основные события, из которых с помощью
операций дизъюнкции, умножения и итерации можно составить более сложные
события, соответствующие заданному алгоритму работы автомата. За основные
события принимают такие события, которые более часто встречаются в инженерной
практике при синтезе схем ЦВМ. |
||