Федеральное агентство по образованию
ФГВОУ ВПО “Уральский Федеральный университет имени первого Президента России Б.Н. Ельцина”
Кафедра «Информационные технологии»
Синтез структурного автомата
Курсовой проект
По дисциплине «Теория автоматов»
Вариант № 1
Преподаватель: Битюцкий В.П.
Студент: Дуборенко М.И
Группа: Р-200210
2012
Содержание
1. Постановка задачи 4
2. Минимизация автомата 5
3. Декомпозиция автомата 6
4. Синтез структурного автомата каноническим методом 11
Заключение 14
1. Постановка задачи
Для заданного автомата:
1. декомпозировать его на автоматы с двумя состояниями;
2. синтезировать автомат классическим методом.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
z1 |
9/w1 |
6/w1 |
2/w1 |
--/w2 |
8/w2 |
5/w2 |
6/w1 |
5/w2 |
8/w2 |
z2 |
--/-- |
7/w1 |
9/w2 |
6/w1 |
3/w2 |
7/w2 |
2/w1 |
1/w2 |
--/-- |
z3 |
7/w1 |
6/w2 |
4/w2 |
3/w1 |
9/w2 |
9/w1 |
1/w1 |
2/w1 |
5/w2 |
z4 |
3/-- |
--/-- |
5/w2 |
5/w2 |
--/-- |
--/-- |
4/w2 |
1/w2 |
9/w2 |
Счётный триггер и классический базис {2-И, 2-ИЛИ, НЕ}.
2. Минимизация автомата
Задачу минимизации частичного автомата S можно сформулировать как задачу поиска автомата S', который среди всех автоматов, покрывающих S, имеет наименьшее число состояний.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
z1 |
9/w1 |
6/w1 |
2/w1 |
--/w2 |
8/w2 |
5/w2 |
6/w1 |
5/w2 |
8/w2 |
z2 |
--/-- |
7/w1 |
9/w2 |
6/w1 |
3/w2 |
7/w2 |
2/w1 |
1/w2 |
--/-- |
z3 |
7/w1 |
6/w2 |
4/w2 |
3/w1 |
9/w2 |
9/w1 |
1/w1 |
2/w1 |
5/w2 |
z4 |
3/-- |
--/-- |
5/w2 |
5/w2 |
--/-- |
--/-- |
4/w2 |
1/w2 |
9/w2 |
По таблицам переходов и выходов автомата составляется треугольная таблица, столбцы и строки которой сопоставляются с состояниями автомата. Вид таблицы обусловлен рефлексивностью и симметричностью отношения совместимости состояний - она треугольная. Для упрощения записи в этой таблице вместо ai будем писать i.
В треугольной таблице на пересечении строки m и столбца s ставятся:
Х (крест), если состояния am и as несовместимы по выходу;
множество всех пар состояний, следующих за парой (am, as) и отличных от неё т.е. те пары, совместимость которых необходима для совместимости пары (am, as);
V (птичка), если за (аm, аs) не следуют пары, отличные от (аm, аs), т.е. пара (аm, аs) совместима без дополнительных условий, налагаемых на совместимость других пар;
2 |
XX |
|
|
|
|
|
|
|
3 |
XX |
XX |
|
|
|
|
|
|
4 |
XX |
XX |
XX |
|
|
|
|
|
5 |
XX |
XX |
XX |
XX |
|
|
|
|
6 |
XX |
XX |
XX |
XX |
XX |
|
|
|
7 |
XX 9.6 3.4 7.1 |
XX |
XX |
XX |
XX |
XX |
|
|
8 |
XX |
XX |
Xx |
XX |
XX |
XX 7.1 9.2 |
XX |
|
9 |
XX |
XX |
XX |
XX |
9.5 |
XX |
XX |
XX |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Для нахождения несовместимых пар состояний (и следовательно совместимых пар тоже) треугольная таблица просматривается по столбцам. Отыскивается первая клетка, отмеченная крестом. Пусть это будет клетка (i, j). Тогда во всех клетках, где есть пара (i, j), ставится крест, а уже рассмотренная клетка (i, j) отмечается вторым крестом. Эта процедура проводится для всех клеток (включая новые), отмеченных одним крестом, и заканчивается, когда таких клеток не остаётся. В этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами – несовместимым.
Ф={{9,5},1,2,3,6,7,8}={1,2,3,4,5,6,7,8}
Минимизированный автомат
/ |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
z1 |
8/w2 |
1/w1 |
6/w1 |
3/w1 |
--/w2 |
1/w2 |
6/w1 |
1/w2 |
z2 |
4/w2 |
--/-- |
7/w1 |
1/w2 |
6/w1 |
7/w2 |
3/w1 |
2/w2 |
z3 |
1/w2 |
7/w1 |
6/w2 |
5/w2 |
4/w1 |
1/w1 |
2/w1 |
3/w1 |
z4 |
1/w2 |
4/-- |
--/-- |
1/w2 |
1/w2 |
--/-- |
5/w2 |
2/w2 |