МОТС ЛР1. Ой строки и j
![]()
|
Цель лабораторной работы освоить основные понятия теории автоматов и основные методы анализа и синтеза конечных автоматов на абстрактном уровне. Автоматы в лабораторной работе заданы автоматной таблицей, в которой строки представляют собой состояния, а столбцы – буквы входного алфавита: на пересечении i-ой строки и j-го столбца стоит номер состояния, в которое переходит автомат из i-го состояния по j-ой входной букве, и через запятую – буква выходного алфавита, появляющаяся при этом на выходе автомата (для автоматов Мили). В таком же виде следует представлять и результаты заданий (где это необходимо). 1. Разложить заданный автомат А на автономные: а) по входным буквам ![]() ![]() Строим граф: ![]() Из автомата с входным алфавитом X =x1, x2 может быть построено 2 различных автономных по входу автоматов исключением из графа переходов автомата всех ребер, кроме ребер с x1 либо x2 ![]() ![]() ![]() ![]() ![]()
б) ![]() ![]() ![]() ![]()
2. По автомату Мили построить эквивалентный ему автомат Мура, используя теорему 4.2.2 [1]. ![]() Пусть конечный автомат Мили имеет функцию переходов fq(q, x) и функцию выходов fb(q, x). Найдем функцию переходов fb(b, x) и выходов b(b) автомата Мура, эквивалентного заданному автомату Мили. Поставим в соответствие каждой паре, включающей состояние qi и входной сигнал xj автомата Мили, состояние bij автомата Мура. Кроме того, в множестве состояний автомата Мура включим начальное состояние q0 автомата Мили, обозначив его через b0.
Такое соответствие представляется в виде таблицы кодирования.
Таблицу переходов эквивалентного автомата Мура строим в такой последовательности. 1. Выписать из таблицы кодирования состояния автомата Мили и соответствующие каждому состоянию множества состояний автомата Мура: 1 = {b0, b12} 2 = {b01, b02, b11}. 2. Если состояние bij входит в множество, соответствующее состоянию qр, то в колонку таблицы переходов автомата Мура для состояния bij следует записать состояния, находящиеся в колонке для qр (таблицы кодирования). Чтобы отметить выходными сигналами состояния достаточно наложить таблицу выходов автомата Мили на таблицу кодирования состояний автомата Мура и каждое состояние отметить тем выходным сигналом, с которым оно совпадает.
3. По автомату Мура построить эквивалентный ему автомат Мили. ![]() Таблицы переходов автомата Мили и эквивалентного ему автомата Мура совпадают. Таблица выходов автомата Мили составляется так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке.
4. Найти автоматные отображения слов для заданного автомата, предполагая, что: а) функция выхода обычная (автомат 1-го рода); б) функция выхода сдвинутая (автомат 2-го рода). ![]() а) q(t) = (q(t-1),x(t)), y(t) = (q(t-1),x(t)), S(qi,xj) = (qi,xj) S(qi, xxj) = S(qi, x ) (( qi, x),xj) –автоматное отбражение. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() б) q(t) = (q(t-1),x(t)), y(t) = (q(t),x(t)), ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 5. Минимизировать автомат, используя алгоритм Мили. ![]() Шаг 1. Найдём все классы разбиения, для которых ![]() Разбиение Q = {C11,C12, C13}, где C11={1, 9}; C12={2, 5, 6, 7}; C13 = {3, 4, 8}, Состояния 1 и 9 относим к одному классу C11, т.к.: ![]() ![]() ![]() Состояния 2, 5, 6 и 7 относим к одному классу C12, т.к.: ![]() ![]() ![]() Состояния 3, 4 и 8 относим к одному классу C13, т.к.: ![]() ![]() ![]() Шаг 2. Найдём разбиения среди выделенных классов, для каждого x которых ![]() Для класса C11, новое разбиение не создаётся, т.к. переходы состояний для каждого x принадлежат одному классу, т.е.: ![]() ![]() ![]() C21={1, 9}; Аналогично, для класса C12, происходит разбиение на: C22={2, 6}; C23={5}; C24={7}; Для класса C13, происходит разбиение на: C25={3}; C26={4}; C27={8}. Шаг 3. Найдём разбиения среди выделенных классов Класс C21 разбивается на: C31={1}; C32={9}; Класс C22 разбивается на6 C32={2}; C33={6}; Остальные классы не разбиваются. Шаг 4. Даёт аналогичное разбиение как на предыдущем шаге — алгоритм закончен. В результате мы получили такое количество классов, как и общее число состояний в исходном автомате. Это означает, что автомат уже минимизирован. 6. Написать формулу в алгебре Клини, задающую событие в алфавите {a, b, c}. Все слова, не начинающиеся на ас или на аb. ![]() И после чего содержат произвольное число символов алфавита: ![]() Либо же слово может состоять из одного символа, следовательно: ![]() 7. Синтезировать автомат (на абстрактном уровне), представляющий регулярное событие. (bc*)* ba Строим источники: Для операции объединения источник будет выглядеть так: ![]() Здесь H1 = (bc*)*b, а H3 = a. ![]() Схематически источник примет такой вид: ![]() Таким образом, источник для заданного события (bc*)* baимеет вид: ![]() В процессе детерминизации, получаем граф автомата удовлетворяющий исходному событию: ![]() 8. Провести анализ автомата (написать выражение регулярного события, представляемого автоматом). Начальное состояние – 1, заключительное – 4. ![]() Строим граф: ![]() Проведя анализ графа автомата, находим регулярное событие: a*∙((b∙c∙(ab)*∙c) c)∙(bc)* Вывод: в ходе выполнения лабораторной работы были освоены основные понятия теории автоматов и основные методы анализа и синтеза конечных автоматов на абстрактном уровне. |