Лабораторная работа №2 Конечные детерминированные автоматы. Преобразование недетерминированного конечного автомата к детерминированному Теоретическая часть

Конечный автомат представляет собой пятерку

где, Q - конечное множество состояний автомата,

T - непустое конечное множество входных символов, входной алфавит,

- начальное состояние,

- непустое множество заключительных состояний автомата,

t- переходная функция

Такой автомат работает как распознаватель следующим образом (рис.1). На ленте записана входная строка, ограниченная с двух сторон концевыми маркерами. Управляющее устройство находится в начальном состоянии . Входная лента последовательно просматривается слева направо по одному символу. Допустим, что с помощью считывающей головки оказались просмотрены символы и управляющее устройство находится в состоянии . Символ допускается, если существует хотя бы одно состояние .

Рис. 1

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

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

Множество всех строк T(A), допускаемых автоматом A, может быть записано в виде

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

Каждому состоянию множества Q соответствует одна вершина множества V.

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

На начальную вершину, соответствующую начальному состоянию автомата, указывает стрелка.

Заключительная вершина изображается прямоугольником.

Ребро существует на графе, если для символа и состояния значение функции не пусто и равно .

На рис. 2 изображен граф состояний автомата A.

, где

Рис. 2

Рассмотрим еще один пример грамматики, порождающей следующие предложения языка

Построим для этой грамматики конечный автомат. Граф его состояний приведен на рис. 3.

Рис. 3

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

Как известно, недетерминированный автомат достаточно сложно использовать для разбора. Поэтому интересует возможность преобразования недетерминированного автомата в детерминированный. Для конечных автоматов этот вопрос решается положительно. Доказано, что, если A - недетерминированный автомат, то существует детерминированный автомат A', такой, что . Допустим, что функция переходов имеет множество значений . Будем считать это множество одним новым состоянием q'. Присоединим это состояние к множеству состояний Q автомата, т.е. . Определим функцию перехода для нового состояния q'.

для всех

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

Введем новое состояние и перепишем функции перехода.

так как одно состояние из f - конечное, а

Граф состояний полученного детерминированного автомата показан на рис. 4.

Рис. 4

Следует заметить, что детерминирование автомата не должно изменить множество предложений (или входных строк), которые этот автомат разбирает.

Задание на лабораторную работу

Написать программу, реализующую работу конечного автомата.

Входные данные:

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

q<N>,<C>=<q|f><N>

Здесь символ q обозначает состояние автомата, f – конечное состояние автомата, <N> - произвольное число, обозначающее номер состояния, <C> - один символ.

Пример: q12,g=f0 – запись означает, что если автомат находится в состоянии №12 и читает с ленты символ ‘g’, то он перейдёт в конечное состояние с номером 0

Дополнительные условия

Количество строк в файле (возможных переходов) – неограниченное количество

Начальное состояние автомата (с которого начинается его работа) – q0

Строки в файле не обязаны быть отсортированы по какому-либо критерию

Состояния автомата необязательно нумеруются последовательно

2. строка символов, которую нужно проанализировать с помощью построенного автомата и дать заключение о возможности (или невозможности) разбора этой строки с помощью данного автомата

Пример: строки ab, abc, ba допускаются автоматом, граф переходов которого изображён на рис. 2. Строки b, ak, bad этим автоматом не допускаются.

Выходные данные:

1. Заключение о детерминированности или недетерминированности заданного автомата.

2. В случае недетерминированного автомата вывести переходы для соответствующего ему детерминированного автомата (в виде, соответствующем входному файлу).

3. Заключение о возможности (невозможности) разбора автоматом введённой строки символов

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

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

Весьма неплохо было бы при написании программы использовать возможности объектно-ориентированного программирования. В качестве дополнения, например, можно графически представить граф переходов для автомата до и после проведения операции детерминирования.

При возникновении неоднозначности в оценке, может быть предложено в качестве дополнительного задания сделать файл для автомата, разбирающего какую-то строку (например, if (a>b) exit(1);).

Литература

При подготовка данной лабораторной работы были использованы лекции Тимофеева П.А. по курсу «Теория алгоритмических языков и компиляторов».

Приложения

1. Пример входного файла для автомата, разбирающего строку for ([abc] = [0-9]; [abc] [<|>] [0-9]; [abc]++)

Здесь [abc] – строка произвольной длины, состоящая из символов a, b, c, A, B, C

[0-9] – строка произвольной длины, состоящая из символов цифр

[<|>] – или символ “<”, или символ “>”

q0, =q0

q0,f=q1

q1,o=q2

q2,r=q3

q3, =q3

q3,(=q4

q4, =q4

q4,i=q5

q5,n=q6

q6,t=q7

q7, =q7

q7,a=q8

q7,b=q8

q7,c=q8

q7,A=q8

q7,B=q8

q7,C=q8

q8,a=q8

q8,b=q8

q8,c=q8

q8,A=q8

q8,B=q8

q8,C=q8

q8,==q10

q8, =q9

q9, =q9

q9,==q10

q10, =q10

q10,0=q11

q10,1=q11

q10,2=q11

q10,3=q11

q10,4=q11

q10,5=q11

q10,6=q11

q10,7=q11

q10,8=q11

q10,9=q11

q11,0=q11

q11,1=q11

q11,2=q11

q11,3=q11

q11,4=q11

q11,5=q11

q11,6=q11

q11,7=q11

q11,8=q11

q11,9=q11

q11,;=q13

q11, =q12

q12, =q12

q12,;=q13

q13, =q13

q13,a=q14

q13,b=q14

q13,c=q14

q13,A=q14

q13,B=q14

q13,C=q14

q14,a=q14

q14,b=q14

q14,c=q14

q14,A=q14

q14,B=q14

q14,C=q14

q14, =q15

q14,<=q16

q14,>=q16

q15, =q15

q15,<=q16

q15,>=q16

q16, =q16

q16,0=q17

q16,1=q17

q16,2=q17

q16,3=q17

q16,4=q17

q16,5=q17

q16,6=q17

q16,7=q17

q16,8=q17

q16,9=q17

q17,0=q17

q17,1=q17

q17,2=q17

q17,3=q17

q17,4=q17

q17,5=q17

q17,6=q17

q17,7=q17

q17,8=q17

q17,9=q17

q17, =q18

q17,;=q19

q18, =q18

q18,;=q19

q19, =q19

q19,a=q20

q19,b=q20

q19,c=q20

q19,A=q20

q19,B=q20

q19,C=q20

q20,a=q20

q20,b=q20

q20,c=q20

q20,A=q20

q20,B=q20

q20,C=q20

q20, =q21

q20,+=q22