Алгоритм 3.2. Объединение эквивалентных состояний КА

 

Вход: КА без недостижимых состояний.

Выход: минимальный КА .

 

Шаг 1. На первом шаге строим нулевое разбиение R (0), состоящее из двух классов эквивалентности: заключительные состояния КА - Z и не заключительные - Q - Z.

Шаг 2. На очередном шаге построения разбиения R (n) в классы эквивалентности включить те состояния, которые по одинаковым входным символам переходят в n -1 эквивалентные состояния, т.е.

.

 

Шаг 3. До тех пор, пока R (n) ¹ R (n -1) полагаем n:= n +1 и идем к шагу 2.

Шаг 4. Переобозначить оставшиеся неразбитые группы состояний и включить их в таблицу новых обозначений состояний автомата.

Шаг 5. Определить эквивалентный КА в новых обозначениях.

 

Пример 3.2. Минимизировать конечный автомат из примера 3.1.

 

Последовательность построения разбиений будет иметь вид:

 

R (0) = {{ A, B, C }, { D, E }}, n = 0;

R (1) = {{ A }, { B, C }, { D, E }}, n = 1;

R (2) = {{ A }, { B, C }, { D, E }}, n =2.

Т.к. R (1) = R (2), то искомое разбиение построено.

 

Переобозначим оставшиеся неразбитые группы состояний:

X ={ B, C }, Y ={ D, E }.

Получим минимальный автомат , где ={ A, X, Y }, ={ Y }.

 

Функция переходов автомата представлена в таблице 3.3.

 

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

 

	A	X	Y
a	X		X
b	X	Y	Y

 

Граф переходов конечного автомата после его минимизации показан на рисунке 3.3.

 

 

 

Рисунок 3.3 – Граф минимального КА

 

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

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

1) ввод исходного конечного автомата и вывод на экран его графа;

2) устранение недостижимых состояний конечного автомата;

3) исключение эквивалентных состояний конечного автомата;

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

Разработать серию контрольных примеров для тестирования реализованных алгоритмов.

Варианты индивидуальных заданий к лабораторной работе № 3 представлены на рисунке 3.4.

0 - 0 - - a a b a b / * b a 1)	) ) 0, 1 ) ( ~ & 2)	a b b a ^ ^ ^ a b c & ~ ~ d d c 3)
m k m m n n / / ! ! m m n n j j j i 4)	^ ^ ] ] { [ } { } { { [ 5)	1, 0 6)
	Рисунок - 3.4 – Варианты индивидуальных заданий к лабораторной работе № 3
18 b   b	8)	9)
10)	11)	12)

Рисунок - 3.4 – Варианты индивидуальных заданий к лабораторной работе № 3, лист 2

4 Лабораторная работа № 4. Эквивалентные преобразования контекстно-свободных грамматик

 

Цель: - закрепить понятия «эквивалентные грамматики», «приведенная КС-грамматика»;

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

 

Основы теории

Определение 4.1. КС-грамматика называется приведенной, если она не имеет циклов, e-правил и бесполезных символов.

Рассмотрим основные алгоритмы приведения КС-грамматик.

Перед всеми другими исследованиями и преобразованиями КС-грамматик выполняется проверка существования языка грамматики.