Обычно автоматом называют устройство, выполняющее без непосредственного участия человека определенную последовательность операций, в результате которой происходит преобразование материальных объектов, энергии или информации. Когда говорится «без участия человека», то подразумевается отсутствие явного управления со стороны человека в ходе выполнения операций. Однако на самом деле управление осуществляется, но опосредованно, через программу, составленную предварительно человеком и заложенную в устройство. В дальнейшем ограничим себя обсуждением лишь тех устройств, которые предназначены для автоматического преобразования информации, представленной в дискретной форме.
Поскольку устройство обменивается информацией с внешней средой, очевидно, оно должно обладать входным каналом, по которому информация поступает в него, а также выходным каналом, через который выдается результат преобразования. Помимо этого, устройство может обладать памятью, в которой фиксируется его текущее состояние; результат обработки в общем случае определяется входными воздействиями и внутренним состоянием устройства. Будем считать, что для представления входной информации используется некоторый конечный алфавит X (входной алфавит), а для представления выходной - конечный алфавит Y (выходной алфавит). Как отмечалось ранее, требование конечности алфавитов является следствием конечности времени обработки информации. Внутренние состояния устройства также образуют дискретный набор, который можно считать внутренним алфавитом - будем обозначать его Q. Что касается числа различных внутренних состояний, то пока не будем делать относительно его никаких предположений.
Будем считать также, что поступление входных символов и переключение состояний устройства происходят не непрерывно, а в определенные моменты времени, т.е. дискретно. Если последовательность моментов произвольна, то говорят об асинхронной организации работы элементов устройства, например, набор номера телефона или кода замка. Однако в сложных устройствах чаще используется синхронная организация, при которой моменты поступления и выхода сигналов, а также переключения внутренних состояний следуют друг за другом через один и тот же фиксированный промежуток времени ∆t = const, называемый тактом. Эти моменты задаются с помощью специального устройства - тактового генератора (или генератора синхроимпульсов). Число тактовых импульсов за единицу времени называется тактовой частотой - она является одним из важнейших факторов, определяющих быстродействие устройства. Можно ввести моменты времени t0, t1, t2,..., обозначающие границы тактов (t0 соответствует моменту начала работы). При этом можно считать, что события, относящиеся к такту i - поступление входного символа, изменение внутреннего состояния, формирование и выдача выходного символа - проистекают мгновенно в момент ti.
Устройства, у которых дискретны множества внутренних состояний, входных и выходных сигналов, а также множество моментов времени, в которые поступают входные сигналы, меняются внутренние состояния и выдаются выходные сигналы, называются дискретными.
Примерами дискретных устройств являются наборный диск телефона, кодовый замок, калькулятор, электронные табло и, безусловно, компьютер. По назначению устройства можно объединить в три группы:
· информационные - справочные автоматы, электронные табло, светофоры, устройства аварийной сигнализации и пр.;
· управляющие - кодовый замок, устройство управления лифтом, станки с программным управлением, микропроцессоры фотоаппарата, видео и пр.;
· вычислительные - микрокалькулятор, микропроцессоры компьютеров.
Существуют устройства, осуществляющие деятельность всех трех видов, например, компьютер, автопилот и др.
Для наших рассуждений существенным оказывается то обстоятельство, что символы на выходе и внутренние состояния такого устройства оказываются дискретными функциями входных символов и номеров тактов работы. Введем понятие функции переходов Y, которая будет связывать внутреннее состояние устройства на последующем такте с состоянием и входным символом на текущем такте:
Другими словами, функция переходов показывает, в какое состояние из всех возможных Q перейдет дискретное устройство, если оно находилось в состоянии qi, а на вход поступил символ xi.
Подобным же образом введем функцию выходов Q, которая будет связывать внутреннее состояние устройства и входной символ на текущем такте с выходным сигналом на этом же такте:
Следовательно, функция выходов определяет, какой символ образуется на выходе, если на данном такте определен символ на входе и состояние устройства.
Говорят, что пятеркой компонентов <Х, Y, Q, Ψ, Θ> задается автомат, обеспечивающий преобразование по определенным правилам последовательностей символов входного алфавита в выходную последовательность. Действительно, если принять начальное условие q1 = q0, то рекуррентные соотношения (9.1) и (9.2) определят порядок преобразования конечной последовательности входных символов x0, x1 ..., xn в некоторую последовательность выходных символов той же длины у0, y1,....yn; при этом будет возникать определенная последовательность внутренних состояний q1, q2, ... . В этом и заключается функционирование автомата. Выходной символ, вырабатываемый автоматом на некотором такте i, зависит не только от входного символа, воспринятого на этом же такте, но и от символов, поступивших ранее - они фиксируются в автомате путем изменения его внутреннего состояния. В этом смысле множество внутренних состояний автомата является его внутренней памятью. В зависимости от объема этой памяти выделяются следующие типы автоматов:
· без памяти;
· с конечной памятью;
· с бесконечной памятью.
Забегая несколько вперед, заметим, что автомат с конечной памятью называется конечным автоматом. Отметим также, что функции переходов и выходов имеют обобщающее название автоматные функции.
Что касается дискретных устройств с бесконечной памятью -это чисто модельное теоретическое представление, поскольку никакие реальные устройства бесконечной памятью обладать не могут. Примером автомата с бесконечной памятью может служить машина Тьюринга, в которой, как указывалось в п. 7.3.3, роль памяти выполняет бесконечная (или при необходимости наращиваемая) в обе стороны бумажная лента. Таким образом, можно считать, что автоматом с бесконечной памятью является алгоритм, представленный в форме машины Тьюринга. Поскольку вопросы, связанные с функционированием машин Тьюринга уже рассматривались ранее, в данной главе они обсуждаться не будут.
В реальных дискретных устройствах сигналы и их преобразования могут иметь различную физическую природу (электрическую, механическую, пневматическую и пр.). Однако от этой природы можно отвлечься и изучать только общие законы построения автоматов и правила, определяющие преобразование информации ими. Такие автоматы называются абстрактными. В теории абстрактных автоматов решаются несколько групп проблем:
во-первых, выясняется, какие преобразования возможны в автомате, как их описать, как выполняемые преобразования связаны с числом состояний (т.е. сложностью) автомата, существуют ли неразрешимые автоматом задачи;
во-вторых, исследуются эквивалентные преобразования автоматов; задача эквивалентного преобразования состоит в построении автомата эквивалентного данному, но имеющего иное количество состояний (обычно, меньшее);
в-третьих, рассматривается круг вопросов, в которых определяется строение автомата по характеру и соотношению входных и выходных сигналов (автомат - «черный ящик») - это важная прикладная задача технической диагностики устройств, без которой невозможна их практическая эксплуатация;
в-четвертых, выделяются структурных элементов автоматов и определяются правил построения из них сложных устройств (задача синтеза автоматов) - с этим связана разработка новых автоматов, в частности, компьютеров.
Важным для практики частным случаем являются автоматы, в которых вся информация представлена с помощью двоичного кода, т.е. алфавиты X, Y и Q являются двоичными - такие автоматы называют двоичными или логическими. Последнее название обусловлено тем, что, как показывает теория, при двоичном кодировании любой конечный автомат можно представить в виде комбинации некоторого числа элементов, реализующих логические операции И, ИЛИ, НЕ, а также элементы памяти (задержка и триггер). Объединение элементов называется логической схемой. Важными представляются два обстоятельства: во-первых, работу логических схем можно описать законами и правилами математической логики (т.е. результат действия логической схемы сводится к вычислению значения логического выражения); во-вторых, из данного небольшого набора элементов можно построить любой конечный автомат.