Cтраница 1
Каскадное соединение автоматов Мура снова есть автомат Мура. [1]
Мы можем строить каскадное соединение автоматов, которые сами представляют собой каскадные соединения. [2]
Это приводит к автомату, реализующему SM в виде каскадного соединения автоматов 2м и Тм. [3]
Из содержания работ [2, 3] вытекает, что разложение автомата в каскадное соединение заданных автоматов получить значительно легче, чем разложение в последовательно-параллельное соединение. Таким образом будет получен желаемый результат. [4]
Последовательное и параллельное соединения автоматов представляют собой частные случаи важной конструкции каскадного соединения автоматов. [5]
Сначала отметим, что отображения а, ft удовлетворяют условиям (6.3) и, следовательно, каскадное соединение автоматов F ( A) и F ( A2), отвечающее тройке ( F ( X), а, Р), есть полугрушювой автомат. [6]
Если А - перестановочный автомат, отображения состояния которого порождают группу G, и если Н - нормальный делитель группы G, a G / H - соответствующая фактор-группа, то существует автомат А, представляющий собой каскадное соединение автоматов А. [7]
Позднее будет показано, что нельзя обойтись меньшим множеством компонент. Заметим, что любое каскадное соединение перестановочных автоматов снова будет перестановочным автоматом, поэтому для построения неперестановочного автомата требуется по крайней мере одна неперестановочная компонента. Определим теперь, какие перестановочные компоненты нужны для построения произвольного заданного автомата. [8]
Главная цель этой главы состоит, во-первых, в том, чтобы установить явную связь между понятиями теории автоматов и понятиями теории полугрупп ( исследование автоматов с применением методов теории полугрупп получило в последние годы широкое распространение, но оно недостаточно полно отражено в литературе), во-вторых, дать строгое доказательство интуитивно ясных и важных для дальнейшего изложения результатов. Изображение с помощью диаграмм каскадного соединения автоматов должно, на наш взгляд, помочь читателю получить более простые доказательства известных результатов, а также открывать и доказывать новые факты. [9]
Из простых автоматов строятся более сложные. Основной конструкцией при этом служит каскадное соединение автоматов. Обратной задачей является декомпозиция автоматов; классический результат здесь получен К. Построению автоматных конструкций и вопросам декомпозиции чистых автоматов посвящена гл. [10]
Это завершает доказательство одного шага индукции. Начиная индукцию с тривиального покрытия X, мы получаем последовательность покрытий и перестановочно-возвратных автоматов, которая обрывается, когда мы приходим к покрытию, состоящему из одноэлементных множеств, тем самым автомат А представлен как каскадное соединение перестановочно-возвратных автоматов. На этом заканчивается доказательство основной теоремы. [11]
В § 1 было отмечено, что каждому автомату А - ( А, X, В) отвечает полугрупповой автомат F ( A) ( A, F ( X), В), где F ( X) - свободная полугруппа над множеством X. Рассмотрим связь этого перехода с конструкциями декартового произведения и каскадного соединения автоматов. [12]