22119

Операции в алгебре событий

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Дизъюнкцией событий S1 S2 Sk называют событие S = S1vS2vvSk состоящее из всех слов входящих в события S1 S2 Sk. Произведением событий S1 S2 Sk называется событие S = S1 S2 Sk состоящее из всех слов полученных приписыванием к каждому слову события S1 каждого слова события S2 затем слова события S3 и т. слова входящие в события S1S2 и S2S1 различны: т. Итерацией события S называется событие{S} состоящее из пустого слова e и всех слов вида S SS SSS и т.

Русский

2013-08-04

24.5 KB

3 чел.

Лекция 5

Операции в алгебре событий.

Алгебра событий включает три операции:

  •  Дизъюнкцию (объединение) событий;
  •  Произведение событий;
  •  Итерацию событий.

Дизъюнкцией событий 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 различны: т.е. S1S2S2S1 . Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий 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).

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

 Очевидно любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными.

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

Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений.

Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЦВМ.


 

А также другие работы, которые могут Вас заинтересовать

34281. Задачей медицинской генетики является выявление и профилактика наследственных заболеваний 60.16 KB
  При изучении генетики чаще всего используются такие методы: Генеалогический метод состоит в изучении родословных на основе менделевских законов наследования и пoмoгeт установить характер наследования признака доминантный или рецессивный. Этим методом выявлены вредные последствия близкородственных браков которые особенно проявляются при гомозиготности по одному и тому же неблагоприятному рецессивному аллелю. Близнецовый метод состоит в изучении различий между однояйцевыми близнецами. С помощью близнецового метода выявлена роль...
34282. Изменчивость 48.89 KB
  На основе изменчивости организмов появляется генетическое разнообразие форм которые в результате действия естественного отбора преобразуются в новые виды. Виды: Ненаследственная модификационная фенотипическая В результате изменение условий среды организм изменяется в пределах НОРМЫ РЕАКЦИИ это пределы рамки в которых возможно изменение признака у денного генотипа например норма реакции молочности у коров колеблется от 1000 до 2500 кг заданной генотипом. 2 Наследственная генотипическая а...
34283. Гипотезы происхождения эукариотических клеток 194 KB
  Согласно симбиотической гипотезе популярной в настоящее время корпускулярные органеллы эукариотической клетки имеющие собственный геном характеризуются независимым происхождением и ведут начало от прокариотических клетоксимбионтов. Первоначально объем информации и геномах клеткихозяина с одной стороны и симбионтов презумптивных митохондрий центриолей и хлоропластов с другой был повидимому сопоставим. В дальнейшем могла произойти утрата геномами симбионтов части генетических функций с перемещением блоков генов в геном...
34284. Медицинская экология. Предмет, содержание, задачи и методы. Появление нового типа заболеваний человека – экологически зависимых болезней 13.29 KB
  Появление нового типа заболеваний человека экологически зависимых болезней. Медицинская экология пытается установить причину заболеваний в непосредственной связи с окружающей средой при этом учитывается большое разнообразие экологических факторов нозологических форм заболеваний и генетических особенностей человека. Появился новый тип заболеваний человека который можно назвать экологически обусловленными заболеваниями или как их иногда называют экологически зависимыми экологически связанными заболеваниями. Хронических...
34285. Мута́ция 22.01 KB
  Изменение числа генов: гаплоидия кратное уменьшение числа хромосом у потомства полиплоидия геном представлен 2 наборами хромосом различают аллополиплоидов имеются наборы хромосом полученные при гибридизации от разных видов и аутополиплоидов происходит увеличение числа наборов хромосом собственного генома кратное n. анеуплоидия гетероплоидия изменение числа хромосом не кратное гаплоидному набору 2. Изменение числа хромосом: моносомия отсутствие в хромосомном наборе диплоидного организма одной хромосомы полисомия...
34286. Общая периодизация и характеристика основных этапов постэмбрионального онтогенеза 56 KB
  Влияние генетических факторов условий и образа жизни на процесс старения. Влияние факторов Ряд наблюдений легли в основу достаточно распространенной точки зрения о наследуемости продолжительности жизни и следовательно наличии генетического контроля или даже особой генетической программы старения. Вопервых максимальная продолжительность жизни ведет себя как видовой признак.Описаны наследственные болезни с ранним проявлением признаков старости и одновременно резким сокращением продолжительности жизни.
34287. Онтогене́з 31 KB
  Постэмбриональное развитие Постэмбриональное развитие бывает прямым и непрямым. Прямое развитие развитие при котором появившийся организм идентичен по строению взрослому организму но имеет меньшие размеры и не обладает половой зрелостью. Дальнейшее развитие связано с увеличением размеров и приобретением половой зрелости.