Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Минимизация конечных автоматов





Два автомата называются эквивалентными, если они для любой последовательности символов из входного алфавита X выдают одинаковую последовательность символов из выходного алфавита Y. Переход от автомата M к эквивалентному автомату называется эквивалентным преобразованием автомата M. Можно ставить много задач о поиске автоматов, эквивалентных данному и обладающих заданными свойствами. Наиболее изученной является задача о минимизации числа состояний автомата: среди всех автоматов, эквивалентных автомату M, найти автомат с наименьшим числом состояний (минимальный автомат).

Пусть имеется автомат M=(Q, X, Y, d, l). Рассмотрим алгоритм Мили поиска минимального автомата. На каждом шаге алгоритма будем строить некоторое разбиение множества состояний Q на классы, причем разбиение на каждом шаге алгоритма будет получаться расщеплением некоторых классов предыдущего разбиения.

Шаг 1. Два состояния q и ; относим в один класс C1j, если для каждого символа входного алфавита совпадают выходные символы для этих состояний, т.е. l(q, x)=l(q¢,x).

Шаг i+1. Два состояния q и ; из одного класса Cij относим в один класс Ci+1,j, если для каждого символа входного алфавита осуществляется переход из состояний q и ; в состояния, принадлежащие одному и тому же классу Cis, т.е. d(q, x) и d(q¢,x) принадлежат одному и тому же классу. Если (i+1)-ый шаг не изменяет разбиения, то алгоритм заканчивается. Каждый класс соответствует состоянию минимального автомата.

Пример 5.4. Построим минимальный автомат для автомата, заданного следующей таблицей переходов.

     
  3,0 2,1
  1,1 6,0
  5,0 2,1
  5,1 6,0
  5,0 4,1
  2,0 1,1

 

Шаг 1. Разбиваем множество состояний на два класса по выходным символам:

1, 3, 5, 6 и 2, 4.

Шаг 2. Рассмотрим переходы в новые состояния для класса 1, 3, 5, 6 при входном символе 0:

1, 3, 5, 6 3, 5, 5, 2.

Состояния 3 и 5 принадлежат одному классу, а состояние 2 – другому. Следовательно, делаем разбиение класса 1, 3, 5, 6 на два новых класса: 1, 3, 5 и 6. После этого шага алгоритма имеем три класса: 1, 3, 5; 6 и 2, 4.

Шаг 3. Рассмотрим переходы в новые состояния для класса 1, 3, 5 при входном символе 1: 1, 3, 5 2, 2, 4. Так как состояния 2 и 4 находятся в одном классе, то нового разбиения на этом шаге не получим.

Шаг 4. Рассмотрим переходы в новые состояния для класса 2, 4 при входном символе 0: 2, 4 1, 5. Так как состояния 1 и 5 находятся в одном классе, то нового разбиения на этом шаге не получим.

Шаг 5. Рассмотрим переходы в новые состояния для класса 2, 4 при входном символе 1: 2, 4 6, 6. Нового разбиения на этом шаге не получим.

Окончательно, разбиение на классы имеет вид: 1, 3, 5; 6; 2, 4. Таблица переходов минимального автомата будет иметь следующий вид:

     
  1,0 3,1
  3,0 1,1
  1,1 2,0

 


Состоянию 1 минимального автомата соответствует класс 1, 3, 5, состоянию 2 – класс 6, состоянию 3 – класс 2, 4.

 







Дата добавления: 2015-09-18; просмотров: 986. Нарушение авторских прав; Мы поможем в написании вашей работы!




Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

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

Studopedia.info - Студопедия - 2014-2025 год . (0.014 сек.) русская версия | украинская версия