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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 8Следующая ⇒

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

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

Шаг 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-правил и бесполезных символов.

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

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

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология