Общие теоретические положения
Конечным автоматом (в дальнейшем – просто автоматом) называется система S={A, Q, V,d, l},в которой A={а1, ..., a . m}, Q={q1, ..., qn}, V={v1, ..., vn} — конечные множества (алфавиты), а d: Q´A —> Q иl: Q´A -> V – функции, определенные на этих множествах. А называется входным алфавитом, V – выходным алфавитом, Q – алфавитом состояний, d – функцией переходов, l – функцией выходов. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (обычно будет считаться, что это q1), то полученный автомат называется инициальным и обозначается (S, q ); таким образом, по неинициальному автомату с п состояниями можно п различными способами определить инициальный автомат.
Поскольку функции d и l определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводятся в одну таблицу d´l: Q´A -> Q´V, называемую таблицей переходов автомата, или просто автоматной таблицей.
Пример 1. Таблица 1 задает функции переходов и выходов для автомата с алфавитами А={а1, а2, а3}, Q={ q1, q2, q3, q4}, V={v1, v2}.
Еще один распространенный и наглядный способ задания автомата — ориентированный мультиграф, называемый графом переходов или диаграммой переходов. Вершины графа соответствуют состояниям; еслиd(qi, а j) = qk и l(qj, аj) = vl,то из qi в qj ведет ребро, на котором написаны qj и vl.
Рисунок 1
Задание к работе
Задача № 1
Представлен автомат, распознающий конечный язык A={0, 01, 10, 001, 101, 1100}.
Построить диаграмму (граф)
1
|
Задача № 2
Построить конечные автоматы, распознающие объединение, пересечение и разность языков, заданных конечными автоматами
q1
|
| q0
|
| q2
|
Задача № 3
A. F1={q1}, F2={q3};
B. F1={q0}, F2={q1, q2};
C. F1={q0}, F2={q0, q3}.
| q1
|
Задача № 4
Построить конечный автомат, распознающий конкатенацию языков, заданных конечными автоматами, диаграммы которых представлены на рис., в случаях, когда подмножества «хороших» состояний этих автоматов определяются следующим образом:
A. F1={q1, q2}, F2={q0};
B. F1={q0}, F2={q3};
C. F1={q0, q1}, F2={q0}.
| q1
|
Задача № 5
Построить конечный автомат, распознающий итерацию языка, заданного конечным автоматом, диаграмма которого представлена на рис., в случаях, когда подмножество «хороших» состояний этого автомата определяется следующим образом:
A. F={q1, q2};
B. F={q0, q4};
C. F={q3, q4}.
Задача № 6
Построить конечный автомат, распознающий итерацию языка, заданного конечным автоматом, диаграмма которого представлена на рис., в случаях, когда подмножество «хороших» состояний этого автомата определяется следующим образом:
A. F={q1, q2};
B. F={q0, q4};
C. F={q3, q4}.
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Запишите теорему разложения и её тождества. Покажите на примере, как используются тождества для упрощения логических выражений.
2. Какие способы минимизации Вы знаете? Опишите порядок минимизации одним из этих способов.
3. Как преобразовать функцию в СДНФ в полином Жегалкина и как
выполнить обратное преобразование?
4. Запишите код Грея. Как сделать преобразователь двоичного
кода в код Грея?
5. Докажите равенство 
.
Практическая работа № 26
Тема: Решение задач по теории конечных автоматов. Матрицы переходов.
Цель: отработать навыки в решении задач в теории конечных автоматов, используя графы, матрицы переходы; уметь осуществлять проверку автоматов используя программное обеспечение.
Материальное обеспечение: практическая работа, программное обеспечение.
Дата добавления: 2019-02-22; просмотров: 306; | Поделиться с друзьями:
|
Мы поможем в написании ваших работ!
