2.6. Конечные автоматы и регулярные языки (типа 3)

Конечный автомат — эта машина без динамической памяти. Например, программа на Фортране, в которой не используются ленты со стиранием, определяет конечный автомат, так как у нее нет динамической памяти. Подобным образом программы на Алголе и ПЛ/1, которые не определяют динамических структур данных, можно представить как конечные автоматы, так что этот класс программ имеет немалое практическое значение.

Формально конечный автомат М определяется как пятерка

где — конечное множество внутренних состояний памяти, в том числе и единственное начальное состояние — конечный входной алфавит, — множество заключительных состояний, Р — отображение множества в определяющее правила перехода из одного состояния в другое как функцию текущего состояния и входного символа. Интуитивное представление об организации конечного автомата можно получить из рис. 2.9. Находясь сначала в состоянии система на каждом такте считывает один символ с ленты, продвигает читающую головку на один шаг вправо и переводит статическую память в состояние, определяемое состоянием в данный момент и входным символом. Затем цикл повторяется до тех пор, пока не будет достигнуто некоторое состояние

Машина воспринимает входную цепочку если достигается впервые сразу после прочтения последнего символа из

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

Рис. 2.9. Переход конечного автомата из состояния в состояние после чтения символа

На рис. 2.10 приведен пример. Представление конечного автомата в виде графа непосредственно приводит к одному методу написания соответствующей программы, так как переход от теоретико-графовых

Рис. 2.10. Конечный автомат, представленный в виде матрицы переходов между состояниями. Метка на дуге обозначает символ, считываемый на соответствующем переходе.

операций к операциям над массивами очень прост. Если М — граф, то его можно представить в виде матрицы связностей С, где

Для чтения матрицы С и описания действий определяемого конечного автомата достаточно очень простой программы управления.

Язык воспринимается конечным автоматом тогда и только тогда, когда -регулярный язык (типа 3).

Рис. 2.11. Элементы графа, соответствующие различным типам правил в конечных автоматах.

Напомним, что правила регулярного языка имеют вид

или

где х — терминальный символ, А и В — переменные. - Правило (30а) можно интерпретировать так:

Если в состоянии 5 читается символ х, то перейти в состояние из

Правило (306) интерпретируется так:

Если в состоянии читается символ х, то перейти в

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

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

На практике часто бывает важным следующий результат:

Если L - конечное множество цепочек в то L может порождаться регулярной грамматикой.

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