Cтраница 1
Теории автоматов посвящена обширная литература различного уровня сложности. В указанной литературе рассматриваются в основном синхронные и асинхронные потенциальные автоматы. [1]
Теория автоматов относится к теории графов, грубо говоря, как физиология к анатомии, и для ознакомления с работами 1962 года по автоматам нужен отдельный обзор, не менее объемистый, чем по чистой теории графов. Сюда же примыкают работы Ал. Маркова [38, 39] и ( Глебского [13] по теории кодирования, работы Бэрнеса [76] и ( Петер 179 ], связанные с машинным переводом. Сэлтон [191] иХиб - бард [144] широко Применяют деревья; естественно применение графов Влэдуцом и Сейфером pi ] при развитии машинных информационно-логических методов в химии. Пуаен и Пор [182] в терминах графов дают критерий того, что обработанный на машине манускрипт является первоначальным, а не копией. Смоленский [54] предлагает способ кодирования графов. [2]
Теория автоматов представляет собой независимо и интенсивно развивающуюся область математики, примыкающую к алгебре, теории алгоритмов и комбинаторике. [3]
Теория автоматов представляет собой раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами, прототипами которых являются различные реальные устройства. [4]
Теория автоматов действительно обеспечивает возможность представления любого поведения в виде физического устройства. Однако возникает вопрос, что именно нужно реализовать в структуре автомата, чтобы получить элементы искусственного интеллекта - конкретное поведение человека или животного, например поведение обезьяны, строящей пирамиды из ящиков. [5]
В теории автоматов вводятся понятия полной системы переходов и полной системы выходов автомата. Если для двух любых состояний 7г и / j автомата имеется входной сигнал, переводящий автомат из состояния 7 - в q, то такой автомат называется автоматом с полной системой переходов. Автомат Мура имеет полную систему выходов, если выходные сигналы различны для всех его состояний. [6]
В теории автоматов обычно выделяют несколько этапов ( уровней), среди которых особое значение имеют абстрактный и структурный этапы. [7]
В теории автоматов вводятся понятия полной системы переходов и полной системы выходов автомата. Если для двух любых состояний Qi и QI автомата имеется входной сигнал, переводящий автомат из состояния Q, в Q /, то такой автомат называется автоматом с-полной системой переходов. Автомат Мура имеет полную систему выходов, если выходные сигналы различны для всех его состояний. [8]
В теории автоматов обязательным условием удобства формализованного языка является наличие алгоритма, решающего общую проблему синтеза автомата, описанного на этом языке. Практически это условие не является определяющим, так как Заказчика не интересует синтез любого устройства и путем задания дополнительных ограничений ( сужение класса задач, подлежащих решению) всегда можно добиться того, что алгоритм синтеза существует. Выразительность же языка является на практике, по-видимому, главным условием. Будем в дальнейшем полагать, что Заказчик и Исполнитель нашли общий язык, формализованный и удобный ровно в той мере, в какой это их обоих устраивает. В результате у Исполнителя имеется полная информация о синтезируемом автомате, например, в виде конечных таблиц или диаграмм переходов. На этапе структурного синтеза Исполнитель должен предъявить схему, реализующую заданный оператор, которая должна удовлетворять ряду ограничений. Очевидно, каждое из них может выступать в роли показателя качества решения задачи синтеза. [9]
В теории автоматов вводятся понятия полной системы переходов и полной системы выходов автомата. Если для двух любых состояний QI и QJ автомата имеется входной сигнал, переводящий автомат из состояния Qt в Qp то такой автомат называется автоматом с полной системой переходов. Автомат Мура имеет полную систему выходов, если выходные сигналы различны для всех его состояний. [10]
Для теории автоматов с магазинной памятью основной является следующая теорема. [11]
В теории автоматов любое множество ( конечное или бесконечное) слов некоторого алфавита принято называть событием. Скажем, что рассмотренное выше событие 7 представимо множеством Q в вероятностном автомате с точкой сечения Я. То есть в представимое событие 7 входят те и только те слова, после подачи которых на вход вероятностного автомата его внутреннее состояние оказывается в множестве Q с вероятностью, превышающей К. В этом случае любая точ-ка Q iKi l является изолированной точкой сечения. [12]
В теории автоматов описанные шесть объектов А X, Y, S, s0 k, 8 принято называть конечным автоматом Мили. [13]
В теории автоматов вводятся понятия полной системы переходов и полной системы выходов автомата. Автомат Мура имеет полную систему выходов, если выходные сигналы различны для всех его состояний. [14]
В теории автоматов - характеристика автомата, который, считав первые k входных символов, сразу выдает первые k символов выходной последовательности. [15]