Задание - автомат
Cтраница 2
Следует отметить одну особенность способов задания автоматов. [16]
В табл. 2.40 дан пример задания автомата Мили в форме таблиц переходов и выходов. Столбцы таблиц приписаны отдельным состояниям автомата, строки - входным сигналам. На их пересечении в таблице переходов указано новое состояние, в которое переходит автомат, в таблице выходов - выходной сигнал. [17]
Первоначальные таблицы переходов удобно использовать для задания автоматов, исходя из словесного описания их законов функционирования. Часто возможно довольно легко определить, сколько устойчивых состояний должен иметь автомат для каждого состояния входа i в отдельности. В этом случае устойчивые состояния размещаются в таблице переходов так, чтобы в каждой строке было по одному устойчивому состоянию. Затем все оставшиеся клетки на основании словесного описания работы автомата заполняются неустойчивыми состояниями, задающими простые переходы между устойчивыми состояниями, в результате чего и получается первоначальная таблица переходов. В силу этого такая таблица всегда определяет автомат, функционирующий в соответствии с заданным законом. [18]
Понятие абстрактного автомата будет дано ниже с помощью одного из способов задания автоматов. [19]
Для решения этой задачи прежде всего необходимо описать условия функционирования автомата на некотором формальном языке, то есть ввести стандартную форму задания автоматов. В предыдущем разделе рассмотрены две таких стандартных формы задания автоматов с помощью графов и с помощью функций переходов и выходов. [20]
В случае задания автомата А графом для получения графа автомата В достаточно обозначить выходными сигналами не вершины графа, а стрелки, входящие в соответствующие вершины. [21]
Автоматное отображение XS - S-Y задается, как правило, в виде графа переходов Gn S, ( U, ( X, У)), ( U S2), вершины которого взаимно однозначно соответствуют внутренним состояниям автомата, а дуги-переходам между ними, причем каждая дуга взвешена парой векторов ( X, У), при которой этот переход осуществляется. В целях упрощения задания автомата параллельные дуги графа переходов могут склеиваться. В этом случае некоторые компоненты входных и выходных векторов обозначаются символом -, указывающим на то, что при осуществлении данного перехода значение сигнала, приписанного данной компоненте вектора, несущественно для функционирования устройства. У асинхронного автомата каждая дуга графа переходов дублируется в концевой вершине петлей, взвешенной той же парой векторов ( X, Y), что и соответствующая дуга. Для графа переходов синхронного автомата это условие может не выполняться. [22]
При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. [23]
Для решения этой задачи прежде всего необходимо описать условия функционирования автомата на некотором формальном языке, то есть ввести стандартную форму задания автоматов. В предыдущем разделе рассмотрены две таких стандартных формы задания автоматов с помощью графов и с помощью функций переходов и выходов. [24]
D, О, и имеется автомат, заданный либо системой функций возбуждения элементарных автоматов и функций выходов, либо матрицей соединений. Требуется получить программы настройки ВС для указанных способов задания автомата. [25]
Закон функционирования автомата часто может быть задан в описательной форме - на обычном языке. Поскольку такая форма не является математически строгой, то принципиально нельзя получить алгоритм перехода от описательной формы задания автомата к стандартной. Такой переход должен осуществляться интуитивно. Поэтому стандартная форма задания автомата должна быть достаточно удобной не только для решения задачи синтеза, но и для перехода к ней от различных других форм задания автоматов и, прежде всего, от описательной формы. На этапе структурного синтеза в качестве такой стандартной формы задания автоматов обычно используют кодированные буквами соответствующих структурных алфавитов таблицы переходов и выходов. Кроме того, задают или выбирают набор элементарных автоматов и логических элементов. В результате выполнения этапа структурного синтеза получают структурную схему автомата, то есть способ соединения между собой элементарных автоматов и логических элементов, обеспечивающий заданные условия функционирования автомата. [26]
На рис. 5 приведен декодирующий автомат для кодирования й ioi % oi построенный по методу, описанному выше. Для задания автомата использована развернутая диаграмма, представляющая собой ориентированное дерево. [27]
 |
Фрагмент таблицы переходов для станции протокола HDLC. [28] |
Графическое задание в виде диаграммы состояний наглядно отражает изменение режимов функционирования станции при поступлении тех или иных входных сигналов через интерфейсы I и II. Вместе с тем недостаток диаграммы состоит в том, что она не отражает выходных сигналов через интерфейсы I и II. По этой причине удобно воспользоваться табличной формой задания автомата Мили - таблицей переходов. Из фрагмента таблицы переходов, отражающего реакцию станции, находящейся в состоянии /) 4, на входные сигналы ( рис. 4.26) следует, что при нахождении станции протокола в состоянии D4 и поступлении входного сигнала h2 происходит переход станции в состояние D с одновременной выдачей сигналов с, с4 и C Q. Поступление же сигналов Ih, Ih, AS, fi, v2 или v7 не изменяет состояния станции и не вызывает выдачу ответных сигналов. [29]
Закон функционирования автомата часто может быть задан в описательной форме - на обычном языке. Поскольку такая форма не является математически строгой, то принципиально нельзя получить алгоритм перехода от описательной формы задания автомата к стандартной. Такой переход должен осуществляться интуитивно. Поэтому стандартная форма задания автомата должна быть достаточно удобной не только для решения задачи синтеза, но и для перехода к ней от различных других форм задания автоматов и, прежде всего, от описательной формы. На этапе структурного синтеза в качестве такой стандартной формы задания автоматов обычно используют кодированные буквами соответствующих структурных алфавитов таблицы переходов и выходов. Кроме того, задают или выбирают набор элементарных автоматов и логических элементов. В результате выполнения этапа структурного синтеза получают структурную схему автомата, то есть способ соединения между собой элементарных автоматов и логических элементов, обеспечивающий заданные условия функционирования автомата. [30]
Страницы: 1 2 3