Произвольный автомат

Cтраница 1

Произвольные автоматы первого рода мы будем, как отмечено в § 4 гл. I, называть в дальнейшем автоматами Мили, а частный случай автоматов второго рода, у которых сдвинутая функция выходов К ( а х) не зависит от второй переменной х - автоматами Мура. Автомат будет называться конечным или бесконечным в соответствии с тем, конечно или бесконечно множество его состояний. [1]

Гомоморфизм произвольного автомата ( А, Г, В) в Aim1 ( А, В) означает переход к соответствующему точному автомату, а гомоморфизм его в Atm2 ( T, В) - к соответствующему приведенному автомату. [2]

Для произвольного автомата А множество S всех входных слов, вызывающих появление выходных слов, которые оканчиваются одной и той же буквой ( выходным сигналом) у, называется событием, представленным в автомате А выходным сигналом у. Множество, состоящее из событий S для всех букв выходного алфавита автомата А, называется каноническим множеством событий данного автомата А. [3]

Пусть дан произвольный автомат А с п состояниями. Если матрицы Rz не являются правильными клеточными матрицами соединений, то, применяя стандартный прием, представим каждую из них правильной клеточной матрицей соединений с числом запретов в каждой из матриц Rz, равным фог. [4]

Пусть даны произвольные автоматы А и В с входными алфавитами Х и Х2 и выходными алфавитами У. [5]

Чтобы иметь возможность синтезировать произвольные автоматы при минимальной затрате элементов памяти, целесообразно в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов, которые для краткости будем называть полными автоматами. Полнота системы переходов означает, что для любой пары состояний автомата найдется входной сигнал, переводящий первый элемент этой пары во второй. Это требование эквивалентно требованию: в каждом столбце таблицы переходов должны встречаться все состояния данного автомата. Полнота системы выходов в случае автоматов Мура означает, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. Поэтому для полных автоматов Мура естественно просто отождествлять выходные сигналы с соответствующими внутренними состояниями автомата. [6]

Нами рассмотрена абстрактная декомпозиция произвольного автомата. [7]

Следующее предложение дает критерий свободы произвольного автомата. [8]

Иными словами, в циклическом приведении произвольного автомата как вопросы, так и ответы являются однобуквенными. [9]

В этом параграфе излагается канонический метод синтеза произвольных автоматов в универсальной вычислительной среде, использующий идеи, предложенные в работах [15, 16] для криотронной среды. [10]

Основной результат теории декомпозиции Крона-Роудза заключается в том, что посредством собственной декомпозиции произвольного автомата получаются компоненты, являющиеся групповым автоматом или весьма элементарным стягивающим автоматом. [11]

Последовательно-параллельная декомпозиция группового автомата. [12]

Следовательно, эта эквивалентность не зависит от начального состояния, в то время как соотношение между произвольным автоматом и его стандартным групповым автоматом зависит от начального состояния. Заметим также, что в двух построенных нами автоматах, а также в их последовательно-параллельном соединении между входом и выходом имеется задержка на единичный элемент времени. [13]

Абстрактная теория автоматов без памяти совершенно тривиальна, а структурная теория таких автомате много легче, чем теория произвольных автоматов с памятью. Основная идея излагаемой методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза автомата к задаче синтеза комбинационных схем. [14]

Для произвольного автомата А е 91, индуцирующего частичное отображение множества слов & ( Х) алфавита X на множество слов 5 ( У) алфавита У, можно определить левый Ех и правый EY единичные автоматы ( см. гл. [15]

Страницы: 1 2