Cтраница 1
Абстрактная теория автоматов близка, таким образом, теории алгоритмов, являясь по существу се дальнейшей детализацией. [1]
Абстрактная теория автоматов без памяти совершенно тривиальна, а структурная теория таких автомате много легче, чем теория произвольных автоматов с памятью. Основная идея излагаемой методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза автомата к задаче синтеза комбинационных схем. [2]
В абстрактной теории автоматов термин конечный автомат употребляется зачастую в несколько ином смысле ( см. далее понятие элементарного автомата, стр. [3]
В абстрактной теории автоматов важное значение имеют задачи анализа и синтеза автоматов, а на структурном уровне на первый план ставится проблема синтеза автоматов, которой посвящено большинство работ, связанных со структурной теорией автоматов. [4]
В рамках абстрактной теории автоматов содержание понятий автомат и машина исчерпывается, по существу, стандартным описанием преобразования информации, которое осуществляется автоматом. В нашем изложении этой концепции соответствуют понятия ограниченно-детерминированного оператора) ( заданного своими каноническими уравнениями) или элементарного автомата. Типичными задачами абстрактной теории автоматов являются задачи с экспериментами над автоматами ( ср. IV), исследование которых продолжено в работах Гинзбурга. [5]
Если в абстрактной теории автоматов везде под автоматом подразумевается абстрактный автомат, заданный либо графоидом, либо матрицей соединений, то в структурной теории автоматов, говоря об автомате, имеют в виду структурную схему, состоящую из элементов некоторого стандартного комплекса, в который входят набор элементарных автоматов и функционально полный набор логических элементов. Поэтому на структурном уровне изучаются методы перехода от гра-фоида или матрицы соединений автомата к структурной схеме автомата, приемы построения схем сложных автоматов из схем элементарных автоматов и логических элементов, рассматриваются способы кодирования состояний, входных и выходных сигналов автомата, различные варианты которых определяют, в конечном счете, сложность структурной схемы автомата при неизменном законе его функционирования. [6]
Основной задачей абстрактной теории автоматов является установление связей, существующих между автоматами и индуцируемыми ими отображениями. Как было показано в § 2 настоящей главы, произвольное автоматное отображение можно задавать представляемыми этим отображением событиями. В связи с этим возникает задача установления связей между событиями и автоматами. [7]
Самоорганизующиеся системы и абстрактная теория автоматов, Журн. [8]
В отличие от абстрактной теории автоматов, в структурной теории как входные, так и выходные каналы рассматриваемых автоматов считаются состоящими, вообще говоря, из нескольких элементарных входных и соответственно элементарных выходных каналов. По всем элементарным каналам могут передаваться лишь так называемые элементарные сигналы. Набор всех возможных для данного автомата элементарных сигналов называется структурным алфавитом этого автомата. Структурный алфавит должен быть непременно конечным. Что касается природы букв ( элементарных сигналов), составляющих структурный алфавит, то в структурной теории автоматов ею обычно не интересуются. [9]
Объектом изучения в абстрактной теории автоматов являются абстрактные автоматы вместе с реализуемыми ими отображениями и событиями. [10]
По сравнению с абстрактной теорией автоматов в структурной теории автоматов делаются дальнейшие шаги в направлении учета большего числа свойств реально существующих дискретных автоматов. Главная отличительная особенность структурной теории автоматов состоит в том, что, в отличие от абстрактной теории, она учитывает структуру входных и выходных сигналов автомата, а также его внутреннюю структуру на уровне так называемых структурных схем. Основной задачей структурной теории является изучение композиции автоматов, то есть методов построения сложных автоматов из автоматов, являющихся относительно более простыми. [11]
Структурная теория автоматов и абстрактная теория автоматов являются двумя различными ступенями о б-щ е и теории автоматов. При синтезе реальных автоматов многие вопросы проще и эффективнее решаются на уровне абстрактной теории. [12]
Такой подход характерен для так называемой абстрактной теории автоматов. [13]
Регулярные сообытия имеют особое значение для абстрактной теории автоматов, поскольку класс регулярных событий совпадает с классом событий, представимых в конечных автоматах. В последующих параграфах докажем это важное предложение; здесь же рассмотрим вопрос о соотношении классов событий, представимых в автоматах Мили и Мура. [14]
Интересно отметить, что исследования в области абстрактной теории автоматов привели к взаимному проникновению понятий и методов теории автоматов, с одной стороны, и алгебры и математической логики - с другой тороны. На этой почве появились исследования, представляющие интерес с точки зрения тематики, традиционной для алгебры и для логики. К ним относятся, например, работы В. М. Глушкова [12], Ю. И. Соркина [ ] и др., в которых изучается связь между автоматами и полугруппами. Бюхи [58]) впервые обратил внимание на то, что идеи теории автоматов адекватны для решения чисто логических задач. [15]