Лекция №5

Введение в теорию конечных автоматов (КА). Формальное определение КА, способы задания, примеры. Свойства и варианты конечных автоматов (КА).

(с77)

Два наиболее распространенных способа задания формального языка - это

1) порождающий, который предполагает наличие алгоритма, последовательно порождающего все правильные предложения языка (грамматики);

2) распознающий (или аналитический), который предполагают наличие алгоритма, определяющего принадлежность любой фразы данному языку (автоматы). Если цепочка принадлежит языку, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе — останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем — это множество всех цепочек, которые он допускает.

Примеры распознавателей:

· Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

· Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-

зависимые языки.

· Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная память (магазин, или стек), работающая по принципу LIFO. Определяет контекстно-свободные языки.

· Конечный автомат (КА). Отличается от МП-автомата отсутствием магазина (т.е. отсутствует внешняя (рабочая) память). Определяет регулярные языки.

Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. (с78)

Автомат – это абстрактное вычислительное устройство (алгоритм), определяющий (вычисляющий) некоторое множество и, возможно, преобразующий его в другое множество. Неформальное описание автоматов выглядит следующим образом: автомат имеет входную ленту, управляющее устройство с конечной памятью для хранения состояний, а также может иметь вспомогательную (рабочую) память и выходную ленты.

Существует два типа автоматов:

1) распознаватели - автоматы без выхода, которые распознают, принадлежит ли входная цепочка заданному множеству L (работа автомата определяется его конечным состоянием);

2) преобразователи - автоматы с выходом, которые преобразуют входную цепочку x в цепочку y при условии, что x ∈ L.

Автомат работает в дискретном времени (измеряется в тактах).

Входную ленту можно рассматривать как линейную последовательность ячеек, причем каждая ячейка может хранить один символ из некоторого конечного входного алфавита и в каждый момент времени лента содержит только конечное число ячеек.

Входная головка в каждый момент времени читает (обозревает) одну ячейку входной ленты. За один такт работы автомата входная головка может сдвинуться на одну ячейку вправо, влево (если МТ и ЛОА) или остаться на месте, при этом она выполняет только чтение, т.е. в ходе работы автомата символы в ячейках входной ленты не меняются (если МТ и ЛОА).

Рабочая лента - это вспомогательное хранилище информации. Данные с нее могут читаться автоматом, могут и записываться на нее.

Управляющее устройство - это программа, управляющая поведением автомата. Оно представляет собой конечное множество состояний вместе с отображением, описывающим, как меняются состояния в соответствии с текущим входным символом, читаемым входной головкой, и текущей информацией, извлеченной с рабочей ленты. Управляющее устройство также определяет направление сдвига рабочей головки и то, какую информацию записать на рабочую ленту.

Автомат работает, выполняя некоторую последовательность рабочих тактов. В начале такта читается входной символ и исследуется информация на рабочей ленте. Затем, в зависимости от прочитанной информации и текущего состояния, определяются действия автомата:

1) входная головка сдвигается вправо, влево (МТ и ЛОА) или стоит на месте;

2) на рабочую ленту записывается некоторая информация;

3) изменяется состояние управляющего устройства;

4) на выходную ленту (если она есть) записывается символ.

Поведение автомата удобно описывать в терминах конфигурации автомата, которая включает в себя:

а) состояние управляющего устройства;

б) содержимое входной ленты с положением входной головки;

в) содержимое рабочей ленты вместе с положением рабочей головки;

г) содержимое выходной ленты, если она есть.

Управляющее устройство может быть недетерминированным. В таком случае для каждой конфигурации существует конечное множество возможных следующих тактов, любой из которых автомат может сделать, исходя из этой конфигурации. Управляющее устройство будет детерминированным, если для каждой конфигурации будет возможен только один следующий такт.

Сложность рабочей ленты определяет сложность автомата. Так, например:

1) машина Тьюринга имеет неограниченную в обе стороны ленту;

2) у линейно-ограниченного автомата длина рабочей ленты представляет собой линейную функцию длины входной цепочки;