All posts by admin

Формализация функционирования сетей Петри заключается в последовательной смене ее маркировок.

Класс терминальных языков сетей Петри: 1. Строго мощнее, чем класс языков, порождаемых регулярными грамматиками .

Определение. МАГАЗИННЫМ АВТОМАТОМ называется формальная система состоящая из 5 (6) объектов , где — конечный алфавит входных знаков;

Для любого языка, порождаемого КС грамматикой существует магазинный автомат, возможно недетерминированный, распознающий (принимающий) строки этого языка. То есть для любого существует такой , что .

Если — язык, принимаемый некоторым, возможно недетерминированным магазинным автоматом , то этот язык может быть порожден КС грамматикой, то есть существует грамматика , такая что .

Для любого непустого регулярного языка , порождаемого регулярной грамматикой , существует конечный автомат , возможно недетерминированный, представляющий (порождающий и распознающий) язык .

«Tempora mutantur, et nos mutamur in illis” (Времена меняются, и мы меняемся вместе с ними) Латинский афоризм

определение: 1. Конечный автомат будем представлять как пятерку объектов: -, где входной алфавит ; — алфавит (множество) состояний содержит n элементов, начиная с нуля ; — выходной алфавит ; -отображения (функция) переходов ; — отображения (функция) выходов

Формулировка: Для любого конечного автомата существует неотличимый от него минимальный автомат единственный с точностью до изоморфизма, имеющий состояний, если множество состояний автомата разбивается на классов эквивалентности . 

a) Пусть задан автомат и известно, что число его состояний . b) Зададим начальное приближение классов эквивалентности и сделаем это следующим образом: два состояния и относим в один класс эквивалентности , если и только если для всех входных знаков . 

Утверждение: Для любого автомата Мили существует неотличимый от него автомат Мура . Доказательство:

Алгебра регулярных событий. Пусть заданы два языка и над некоторым алфавитом . Введем три операции: 1. объединение языков 2. конкатенация языков  

Утверждение: Любой язык, построенный в алгебре регулярных событий (заданный регулярным событием) является языком порождаемым регулярной грамматикой.

Утверждение: Для любого регулярного выражения существует конечный автомат представляющий (распознающий, порождающий) язык, задаваемый этим выражением.

Утверждение: Для любого регулярного выражения существует источник представляющий тот же язык .

Определение 2:асинхронный автомат (источник) — называется такой конечный автомат (источник) у которого все состояния (вершины) устойчивы по каждому входному знаку.

Самый отдаленный пункт… к чему-нибудь да близок, а самый близкий – от чего-нибудь да отдален. Козьма Прутков.

Определение: Комбинационный автомат- это конечный автомат, у которого выходной знак зависит от входного, и не зависит от состояния автомата. 

Пусть задан некоторый конечный автомат К Вопрос : Как представить автомат в виде автоматной сети, возможно состоящий из более простых автоматов, чем исходных ? 

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

Определение: Асинхронным автоматом называется конечный автомат все составляющие которого, устойчивы по всем входным знакам. Это означает, что для всех состояний и .

Определение: Произвольный асинхронный автомат может быть представлен ( реализован ) автоматной сетью, состоящей из двух комбинационных автоматов ? и ? ( без линии задержки ).

Определение: Элемент задержки на один такт, используемый в теореме о структурном синтезе автомата КА, — является асинхронным автоматом.

Представим схему, полученную в результате структурного синтеза синхронного автомата.

DL – триггер. Рассмотрим пример синтеза асинхронного автомата, который называется DL – триггером.

Дискретное устройство – это устройство, функционирующее в дискретные моменты времени и обрабатывающее дискретные сигналы.

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

Идея теоремы состоит в том, что одни и те же схемы можно организовать по-разному:

Ранее было показано, что автоматы можно разделить на: • комбинационные • асинхронные • синхронные