 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Операции в алгебре событий
Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий.
Дизъюнкцией событий называют событие S = S 1 v S 2 v …v SG, состоящее из всех слов, входящих в события S 1, S 2, …, SG.
Пример. Событие S 1 содержит слова x 1, x 1 x 1, x 2 x 1, т.е. S 1 = (x 1, x 1 x 1, x 2 x 1), а
S 2 = (x 2, x 1 x 2). Тогда S = S 1 v S 2 = (x 1, x 2, x 1 x 1, x 1 x 2, x 2 x 1).
Произведением событий называется событие, состоящее из всех слов, полученных приписыванием к каждому слову события S 1 каждого слова события S 2, затем слова события S 3 и т.д.
Пример. При тех же событиях S 1 и S 2, = (x 1 x 2, x 1 x 1 x 2, x 2 x 1 x 2, x 1 x 1 x 2, x 1 x 1 x 1 x 2, x 2 x 1 x 1 x 2). Произведение событий не коммутативно, т.е.. Поэтому следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий можно сказать, что событие S 2 умножено на событие S 1 справа, а событие S 1 на S 2 – слева.
Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными. Итерацией события S называется событие { S }, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности, т.е.:
{ S } = e v S v SS v SSS v …
Пример. S = (x 2, x 1 x 2). Тогда { S } = (e, x 2, x 2 x 2, x 2 x 2 x 2, …, x 1 x 2, x 1 x 2 x 1 x 2, …, x 2 x 1 x 2, x 1 x 2 x 2, …)
При синтезе конечных автоматов важнейшую роль играют регулярные события. Любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными.
Теорема: Любые регулярные выражения и только они представимы в конечных автоматах.
Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений.
Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЭВМ.
Пусть дан конечный алфавит X = (x 1, x 2, …, xm).
Регулярное событие – это любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операций дизъюнкции, произведения и итерации. Регулярное выражение – любое выражение, составленное с помощью операций дизъюнкции, произведения и итерации.
Поиск по сайту: