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

UptoLike

ВУЗ: 

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

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

Рубрика: 

121
δ: Q x A → Q – функция переходов;
q
0
∈ Q – начальное состояние;
F ⊆ Q – конечное множество заключительных состояний.
Функция переходов δ естественным образом обобщается на случай отображе-
ния из Q x A* в Q. Язык L(S), порождаемый конечным автоматом, – это множество
строк над А*, определяемое следующим образом:
L(S) = {a ∈A* | δ(q
0
, a) ∈ F}.
Всякому конечному автомату соответствует язык, а класс всех языков, порож-
даемых конечными автоматами, называется классом регулярных языков. Каждый ав-
томат определяется своим языком. Если два конечных автомата имеют одинаковые
языки, то они эквивалентны.
Основные понятия, используемые для получения регулярного языка по конеч-
ному автомату, применимы и к сетям Петри для образования теории языков сетей
Петри.
В дополнение к сети Петри, определяемой множеством позиций и переходов
(которые соответствуют множеству состояний и функций переходов автомата), необ-
ходимо определить начальное состояние, алфавит и множество заключительных
состояний.
Начальное состояние сети Петри можно определить различными способами.
Наиболее общепринятое определение – считать начальным состоянием произвольную
маркировку µ.
Символы алфавита связаны с переходами, поэтому последовательность запус-
ков переходов порождает строку символов языка. Связь символов с переходами осу-
ществляется функцией помечения: δ: Т → А .
Определение заключительных состояний сети Петри оказывает наибольшее
влияние на язык сети Петри.
Одно из определений взято по аналогии с соответствующим понятием для ав-
томатов – множество заключительных состояний F определяется как конечное мно-
жество заключительных маркировок.
Наиболее изученным классом формальных языков является класс регулярных
языков. Эти языки порождаются регулярными грамматиками и конечными автомата-
ми и характеризуются регулярными выражениями.
Всякий регулярный язык – это язык сети Петри. Доказательством этого служит
то, что всякий регулярный язык порождается некоторым конечным автоматом, а вся-
кий конечный автомат можно преобразовать в эквивалентную сеть Петри.
7.7. Преобразование конечного автомата в сеть Петри
Аппаратное обеспечение ЭВМ можно рассматривать на нескольких уровнях, и
сети Петри могут моделировать каждый из этих уровней. На одном уровне ЭВМ по-
строены из простых устройств памяти и вентилей (низкий уровень); на более высоком
уровне в качестве основных компонент вычислительной системы используются
функциональные блоки и регистры.
На низком уровне вычислительные системы могут быть описаны конечными
автоматами. Автомат – это пятерка (Q, X, Y, δ, λ), где
Q – конечное множество состояний;
Х – конечный входной алфавит;

Страницы