Глава 3. Типы конечных автоматов

Любую конечную последовательность символов из входного или выходного алфавитов далее будем называть соответственно входным и выходным словом. Множество всех входных слов обозначим через А^*. Очевидно, что А^* - счетное множество, поскольку алфавит А конечен. Любое подмножество множества А^* назовем языком. В частности, само множество А^* и его пустое подмножество тоже являются языками. Конечный язык состоит из конечного набора слов. Примером конечного языка является множество из 2ⁿ различных строк фиксированной длины п из нулей и единиц. Бесконечный язык содержит бесконечное число слов. Например, все строки из нулей и единиц (не фиксирован­ной, но конечной длины!) с четным числом нулей образуют бесконеч­ный язык.

Все детерминированные конечные автоматы, изучаемые в теории автоматов, можно разбить на две группы. Одну группу образуют так называемые автоматы-распознаватели. Основной особенностью этих автоматов является то, что множество их состояний V всегда разбивается на два непересекающихся класса: F и V\F. Все состояния из класса F считаются особыми и называются заключительными состояниями. Если на вход такому автомату подать слово w, составленное из символов алфавита A, то может оказаться, что автомат завершит работу в одном из заключительных состояний. В этом случае будем говорить, что автомат распознает данное слово w. Все слова, которые распознает автомат, образуют подмножество множества А^*, т.е. составляют некоторый язык L. Тогда про язык L говорят, что он распознается этим автоматом, или что данный автомат распознает язык L.

Отметим ещё одну особенность автоматов-распознавателей. Поскольку считается, что такой автомат распознает слово w только тогда, когда он завершает работу над этим словом в одном из заключительных состояний, то о результате работы автомата мы судим лишь по его состоянию в момент завершения работы. При этом выходные символы, возникающие в процессе функционирования таких автоматов, особого значения не играют. Следовательно, можно игнорировать выходные сигналы или вообще убрать выходной канал. Поэтому автома­ты-распознаватели иногда ещё называют автоматами без выходов. Их функционирование можно описать только одной функцией - функцией переходов. Из этого следует, что автомат-распознаватель - это система из четырех компонент: (А, V, F,g),где А - входной алфавит, V- множество всех состояний,F - множество заключительных состояний, а g - функция переходов. В диаграмме Мура такого автомата уже не нужно указывать выходные сигналы, а его таблица выходов и переходов преобразуется в более простую таблицу переходов.

Пример 1. Построим диаграмму Мура автомата, который, получая на вход произвольную конечную строку из нулей и единиц, распознает строки с четным числом единиц.

Поскольку на каждом такте работы автомата количество единиц в прочитанной части входной строки либо четно, либо нечетно, то автомат имеет два состояния. Если очередной входной символ - это ноль, то текущее состояние автомата сохранится. Если же входным символом окажется единица, то состояние изменится. Чтобы автомат распознавал язык, составленный из строк с четным числом единиц, надо объявить заключительным состоянием начальное состояние автомата. Таким образом, мы получаем инициальный автомат с начальным и заключительным состоянием v₁ . Табл. 4 является его таблицей переходов. Заметим, что если выбрать начальное и заключительное состояния автомата не совпадающими, то он будет распознавать язык из строк с нечетным числом единиц.

Проверка двоичной строки на четность - распространенная операция в процессах передачи и хранения информации. Например, проверяют на четность кодовые слова в коде Хэмминга после их получения на выходе канала связи. В случае, если при передаче кодового слова произошло инвертирование какого-либо бита, проверка на четность позволяет локализовать и исправить ошибку.

Вторую группу конечных детерминированных автоматов составляют так называемые автоматы-преобразователи. В отличие от автоматов-распознавателей у них всегда задана функция выходов f. Авто­маты-преобразователи посимвольно прочитывают входную последова­тельность и перерабатывают её в выходную последовательность такой же длины. Например, с их помощью можно моделировать процессы алфавитного кодирования информации. Оба автомата, рассмотренные в §2, являются автоматами-преобразователями. Заметим, что любой автомат-распознаватель нетрудно превратить в автомат-преобразователь. Для этого достаточно считать, что выходной сигнал в конце каж­дого такта совпадает с входным сигналом в начале этого же такта, т.е. у(t) = х(t). Полученный таким образом автомат-преобразователь можно использовать для генерации слов, принадлежащих тому языку, который распознавался исходным автоматом-распознавателем.

Когда мы рассматриваем какой-либо конкретный автомат-преобразователь, нам в первую очередь важно знать, какая последовательность получается на выходе этого автомата при заданной входной последовательности. Когда же мы исследуем автомат-распознаватель, нам важно знать лишь состояние, в котором этот автомат закончил работу над заданным словом. Таким образом, автоматы-преобразователи лучше подходят для описания вычислительных устройств, а автоматы-распознаватели - для описания устройств управления.

Среди автоматов-преобразователей особо выделяют автоматы Мура. Это автоматы, у которых функция выходов f не зависит от входного сигнала, т.е.

f (a_i, v_j)=f (a_k, v_j) = bjÎВ

для всех a_i, a_k ÎА и v_jÎV. У автомата Мура для каждого t выход у(t)может зависеть от состояния автомата в начале этого t-то такта, т.е. от (q(t- 1), но не должен зависеть от входного сигнала х(t). Образно говоря, выходные сигналы автомата Мура зависят от входных сигналов лишь с «запаздыванием».

В отличие от автомата Мили, в диаграмме автомата Мура метка на дуге - это не пара символов а_i и f (a_i, v_j). а только один входной символ а_i. При этом символом f (a_i, v_j) помечается сама вершина v_j. Это объясняется тем, что, согласно определению автомата Мура, выходной символ f (a_i, v_j) совпадает у всех дуг, выходящих из одной и той же вершины v_j. В следующем примере рассматривается простейший автомат Мура, который часто используется в качестве строительного блока для более сложных автоматов.

Пример 2. Пусть автомат Мура с начальным состоянием v₁ задан диаграммой (рис.4). Вершина, соответствующая состоянию v₂ помечена нулем, а вершина, отвечающая состоянию v₂, - единицей.

Это означает, что если автомат находится всостоянии v₁ , то любому входному сигналу будетсоответствовать выходной сигнал 0. Если же автомат находится в состоянии v₂, то независимо от входного сигнала на выходе автомата будет 1. Заметим также, что если на вход автомата поступает 0, то из любого состояния автомат переходит в состояние v₁. Если на вход поступает 1, то автомат переходит в состояние v₂. Теперь можно кратко сформулировать правила функционирования этого автомата: в первый такт на выход автомата подается 0, а во все последующие такты выходной сигнал будет совпадать с сигналом, поступившим на вход в предыдущем такте. Такой автомат будем называть единичной задержкой, поскольку он «задерживает» входную строку ровно на один такт. Единичная задержка - это модель простейшего элемента памяти реальных устройств. Задержки используются в линиях обратной связи при необходимости, например, подать на вход автомата сигнал из его же выходного канала.

Ещё один подкласс в классе автоматов Мили - это автономные автоматы (или генераторы). Автономный автомат - это автомат без входа. Он полностью определяется системой из пяти компонент (В, V, F, f, g), где В - выходной алфавит, V - множество всех состояний, F - множество заключительных состояний, а f и g - функции выходов и переходов, причем f и gявляются функциями только одного аргумента - состояния автомата. Генераторы используются, например, для поро­ждения символьных строк в алфавите В. Слово, порожденное авто­номным автоматом, - это последовательность выходных сигналов, которая образуется при завершении работы автомата в любом из заключительных состояний. Далее мы увидим, что при фиксированном начальном состоянии выходное слово, порожденное генератором, зависит лишь от продолжительности его работы. Меняя начальное состояние и (или) число рабочих тактов, можно породить некоторый язык из В^*, т.е. набор слов в алфавите В. Особенности табличного задания и диаграммы Мура автономных автоматов рассмотрим на следующем примере.

Таблица 5

v1	v2	v3	v4	v5
а, v2	c, v3	а, v4	b, v5	c, v3

Пример 3. Пусть автономный автомат с выходным алфавитом В={а,b,с} задан таблицей выходов и переходов (табл. 5).

Каждая клетка верхней строки таблицы содержит текущее состояние автомата, а клетка под ней - соответствующий выходной сигнал и новое состояние. Например, первый столбец показывает, что из состояния v₁ автомат всегда переходит в со­стояние v₂ и выдает сигнал а. На рис. 5 приведена диаграмма Мура этого автомата. Пусть его начальным состоянием является v₁, а заклю­чительными - v₁ и v₂. Тогда за один такт автомат породит слово а, по­скольку перейдет из v₁ в заключи­тельное состояние v₂. Кроме того, он породит пустое слово L (так принято называть и обозначать сло­во нулевой длины). Пустое слово порождается данным автоматом, если он завершает работу в началь­ном состоянии v₁ не успев сделать ни одного такта. Таким образом, данный автомат порождает язык L={L, а}, состоящий из двух слов.

Пусть v₂ начальное, а v₃ заключительное состояние автомата. То­гда за один такт автомат перейдет из v₂ в v₃,и мы получим на выходе слово c. Когда автомат выполнит четыре такта, он снова окажется в заключительном состоянии v₃ и породит слово саbс, а выполнив семь тактов, он выдаст слово саbсаbс и т.д. Следовательно, данный автомат генерирует бесконечный язык L₂={с, саbс, саbсаbс, саbсаbсаbс,...}. Заметим, что все слова этого языка имеют конечную длину, и она вы­ражается числом вида 3k+1, где k = 0, 1, 2 и т.д.

Очень важный подкласс автоматов Мили образуют логические автоматы. Так называются автоматы, у которых входной и выходной алфавиты и множество состояний образованы наборами из нулей и единиц фиксированной длины. Благодаря этому функции переходов и выходов автомата f и g можно считать логическими (булевыми) функ­циями. Схема из функциональных элементов - дизъюнкторов, конъ-юнкторов и инверторов - это логический автомат без памяти и, следо­вательно, с одним состоянием.

Дата добавления: 2015-11-30