Синтез цифровых автоматов. Захаров Н.Г - 121 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

120
систем.
В цветных сетях вводится понятие цвета для фишек. В общем случае может
быть n цветов. В вычислительной технике используются трехцветные сети (n = 3). Та-
кие сети используются для моделирования аппаратных средств.
В сетях с изменяемой структурой кратность ребер не является постоянной.
В самомодифицируемых сетях кратность ребра может задаваться либо нату-
ральным числом N, либо определяться количеством фишек, находящихся во входных
позициях некоторого перехода.
Качественными характеристиками могут быть: отсутствие зацикливаний в
системе, достижение некоторого состояния системы (например, конечного).
Количественными характеристиками являются: время работы некоторого
маршрута в программе, время прохождения сигнала в схеме и т. д.
Во временных сетях переходам ставится в соответствие их времена срабатыва-
ния, либо позициям ставится в соответствие времена нахождения фишек в позициях.
В стохастических сетях указанные характеристики являются вероятностны-
ми, т. е. вводится функция плотности вероятности времен срабатывания переходов
или времен нахождения фишек в позициях.
Предикатные сети – это сети с логическим описанием состояния системы.
7.6. Сети Петри и регулярные языки
Методы анализа сетей Петри позволяют проводить исследования разрешимо-
сти таких основных задач, как достижимость. В частности, одна из областей, в ко-
торых рассматриваются вопросы достижимости – это теория формальных языков.
Используя языки сетей Петри, можно перенести понятия и методы теории формаль-
ных языков на задачи для сетей Петри. И наоборот, методы сетей Петри могут ока-
заться весьма полезными для получения новых сведений о формальных языках.
Языком называется множество строк алфавита. В общем случае, языки могут
быть бесконечными, следовательно, одной из проблем является представление языка.
Для представления языков предложено два подхода. Один заключается в определении
машины, которая порождает строку из языка, и любая строка из языка порождается
ею. Другой подход подразумевает определение грамматики, которая указывает, как
последовательным применением ее правил порождения получаются строки языка.
Ограничения, накладываемые на вид машин или грамматик, порождающих
языки, определяют классы языков.
Традиционными классами языков являются: регулярный, контекстно-
свободный, контекстно-связанный и языки типа 0, соответствующие конечным авто-
матам, магазинным автоматам, линейно-ограниченным автоматам и машинам Тью-
ринга. Каждый из классов языков порождается соответствующим классом автоматов.
Это дает возможность установления связи теории сетей Петри с теорией формальных
языков, чтобы определить класс языков сетей Петри как класс языков, порождаемых
сетями Петри.
Рассмотрим в качестве примера конечные автоматы и регулярные выражения.
Конечный автомат S есть пятерка (Q, А, δ, q
0
, F), где
Q – конечное множество состояний;
А – алфавит символов; А* – множество всех строк из символов А, включая
пустую строку: А* = А ∪{ε};

Страницы