Алгоритм 2. 1. Построение КА по регулярной грамматике

 

Вход: регулярная грамматика .

Выход: КА .

Шаг 1. Пополнить грамматику правилом , где и - новый нетерминал, для каждого правила вида , если в грамматике нет соответствующего ему правила , где .

Шаг 2. Начальный символ грамматики принять за начальное состояние КА . Из нетерминалов образовать множество состояний автомата , а из терминалов – множество символов входного алфавита .

Шаг 3. Каждое правило преобразовать в функцию переходов , где .

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

Шаг 5. Если в грамматике имеется правило , где - начальный символ грамматики, то поместить во множество заключительных состояний.

Шаг 6. Если получен НКА, то преобразовать его в ДКА.

 

Алгоритм 2.2. Преобразование НКА в ДКА

 

Вход: НКА .

Выход: ДКА .

 

Шаг 1. Пометить первый столбец таблицы переходов ДКА начальным состоянием (множеством начальных состояний) НКА .

Шаг 2. Заполняем очередной столбец таблицы переходов , помеченный символами , для этого определяем те состояния , которые могут быть достигнуты из каждого символа строки при каждом входном символе . Поместить каждое найденное множество (в том числе ) в соответствующие позиции столбца таблицы , т.е.:

 

для некоторого }.

 

Шаг 3. Для каждого нового множества (кроме ), полученного в столбце таблицы переходов , добавить новый столбец в таблицу, помеченный .

Шаг 4. Если в таблице переходов КА есть столбец с незаполненными позициями, то перейти к шагу 2.

Шаг 5. Во множество ДКА включить каждое множество, помечающее столбец таблицы переходов и содержащее НКА .

Шаг 6. Составить таблицу новых обозначений множеств состояний и определить ДКА в этих обозначениях.

Пример 2.1. Дана регулярная грамматика с правилами . Построить по регулярной грамматике КА и преобразовать полученный автомат к детерминированному виду.

Решение задачи включает следующую последовательность действий.

1 Построим по регулярной грамматике КА.

1.1 Пополним грамматику правилами и , где - новый нетерминал.

1.2 Начальное состояние конечного автомата . Множество состояний автомата , множество символов входного алфавита .

1.3 Значения сформированной функции переходов даны в таблице 2.1.

 

Таблица 2.1 – Функция переходов автомата

 

	S	A	B	N
a	A, B	A	N
b		N	B

 

1.4 Множество заключительных состояний .

1.5 Для начального символа грамматики e-правила отсутствуют.

Конечный автомат М - недетерминированный, граф НКА представлен на рисунке 2.1 слева.

 

 

Рисунок 2.1 - Граф НКА (слева) и ДКА (справа) для Р- грамматики

 

2 Построим по НКА ДКА .

2.1 Строим таблицу переходов для ДКА (таблица 2.2).

 

Таблица 2.2 – Построение функции переходов для ДКА

 

Шаг
F	S	A, B	A, N	B, N	A	N	B
a	A, B	A, N	A	N	A		N
b		B, N	N	B	N		B

 

2.2 Во множество заключительных состояний автомата включим элементы .

2.3 Введем следующие новые обозначения состояний автомата : (A, B) =С, (A, N)= D, (B, N)= E.

2.4 Искомый ДКА определяется следующей пятеркой объектов: , , функция переходов задана таблицей 2.3, , .

Граф полученного ДКА представлен на рисунке 2.1 справа.

 

Таблица 2.3 – Функция переходов для ДКА

 

	S	A	B	С	D	E	N
a	C	A	N	D	A	N
b		N	B	E	N	B

 

Постановка задачи к лабораторной работе № 2

Разработать программное средство, реализующее следующие функции:

1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принадлежность к классу регулярных грамматик;

2) построение по заданной регулярной грамматике конечного автомата;

3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату;

4) вывод графа результирующего конечного автомата на экран.

Варианты индивидуального задания представлены в таблице 2.4.

 

Таблица 2.4 – Варианты индивидуального задания к лабораторной работе № 2

 

Вариант	Регулярная грамматика
	G =({ S, C, D }, {0, 1}, P, S), где P: 1) S ®1 C | 0 D; 2) C ®0 D | 0 S | 1; 3) D ®1 C | 1 S | 0.
	G =({ S, A, B, C }, { a, b, c }, P, S), где P: 1) S ® aA | bB | aC; 2) A ® bA | bB | c; 3) B ® aA | cC | b; 4) C ® bB | bC | a.

Продолжение таблицы 2.4 – Варианты индивидуального задания к лабораторной работе № 2

 

Вариант	Регулярная грамматика
	G =({ K, L, M, N }, { a, b, +, -, ^}, P, K), где P: 1) K ® aL | bM; 2) L ®- N | - M; 3) M ®+ N; 4) N ®a L | bM | ^.
	G =({ X, Y, Z, W, V }, {0, 1,~, #, &}, P, X), где P: 1) X ®0 Y | 1 Z | e; 2) Y ®0 Z | ~ W | #; 3) Z ®1 Y | 1 W | 0 V; 4) W ®0 W | 1 W | #; 5) V ®& Z.
	G =({ K, L, M, N, Q, P, R, S }, {0, 1, *, $, /}, V, K), где V: 1) K ®1 L | 0 N; 2) L ®0 M | 0 P | / Q; 3) N ®1 R | 1 M | * S; 4) Q ®1 P; 5) P ®* L | $; 6) M ®$; 7) S ®0 R; 8) R ®/ N | $.
	G =({ E, A, B, C, D }, {0, 1, a, b, c }, P, E), где P: 1) E ®0 A |e; 2) A ® aB | aD; 3) B ® bB | 1 C | c; 4) D ® aD | 0 C | c.
	G =({ X, Y, Z, V, W }, {0, 1, x, y, z }, P, X), где P: 1) X ® yY | zZ; 2) Y ®1 V; 3) Z ®0 W | 0 Y; 4) V ® xZ | xW | 1; 5) W ®1 Y | 0.
	G =({ S, A, B, C, D }, { a, b, c, d, ^}, P, S), где P: 1) S ® aA | bB; 2) A ® cC | ^; 3) C ® cC | cA; 4) B ® dD | ^; 5) D ® dD | dB.
	G =({ K, L, M, N, P }, {0, 1, &, %, a, b }, C, K), где C: 1) K ®1 M | e; 2) M ®0 L | & N | & P; 3) L ®1 L | 0 L | % P; 4) N ® aN | bN | % P; 5) P ®1 P | aP | 0.
	G =({ I, J, K, M, N }, {0, 1, ~,!}, P, I), где P: 1) I ®0 J | 1 K | 0 M; 2) J ®~ K | 0 M; 3) K ®~ M | 0 J | 0 N; 4) M ®1 K |!; 5) N ®0 I | 1 I |!.
	G =({ S, A, B, C, D, E }, { a, b, c, d, e, $, ^}, P, S), где P: 1) S ® aA | bB | cC; 2) A ® dD; 3) B ®# D | $ E; 4) D ® dD | dB | ^; 5) C ® cE; 6) E ® eE | eB | ^.
	G =({ X, Y, Z, V }, {(,), y, z, v }, P, X), где P: 1) X ®(Y | e; 2) Y ® yY | zY | zZ; 3) Z ® zZ | vZ | vV; 4) V ® vV |).