Проблемы и задачи, решаемые теорией автоматов. До 30 минут

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

В этой теории достаточно четко выявляются ее направления, обусловленные:

1. выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)
2. принятым уровнем абстракции (абстрактные и структурные автоматы)
3. спецификой применяемых математических (алгебраическая теория автоматов)

При этом в дискретных моделях рассматриваемых объектов учитывается лишь логика происходящих процессов изменений автомата без учета количественных характеристик.

Центральными проблемами читаемой теории являются проблемы синтаксиса и анализа (т.е. разработка функциональной схемы автомата по заданному его поведению и описание поведения автомата по известной его структуре). С этими проблемами тесно связаны задачи полноты, эквивалентности, минимизации числа состояний автоматов.

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

Основные понятия. До 40 минут

1. Абстрактный конечный автомат U - модель <X, Q, Y, R>, представляющая устройство, которое преобразует информацию по правилам R в виде «черного ящика», имеющего входной А и выходной В алфавиты, а также некоторое множество внутренних состояний Q.

x_i Î X_, y_j Î Y, q_k Î Q

Когда на вход подается сигнал a_i, то в зависимости от него и текущего состояния q_k Î Q автомат переходит в следующее состояние q_{l Î} Q и выдает сигнал на выход b_j Î B. Это – один такт действия автомата q_k a_i® q_l b_j. Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

1. Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.
2. Ситохастический (вероятностный) автомат - абстрактный автомат, правила преобразования информации, которого R являются вероятностными.
3. Конечный автомат – дискретный автомат, в котором переход из одного состояния в любое другое может быть совершено за конечное число шагов (таким автоматом, например, является процессор).
4. Структурный автомат - конечный автомат, внутреннее устройство которого известно.
5. Формальная грамматика s=<T, H, J, P> - система правил построения P в заданном алфавите TÈH(T – терминальный алфавит, Н – нетерминальный алфавит, ТÇН=Æ) конечных знаковых последовательностей, множество которых образует некоторый формальный язык a(s) (JÎH, Н - аксиома).
6. Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой s).
7. Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TÈH) обозначать греческими буквами; так, например, aÎ (TÈH)*).
8. Предложение – слово в терминальном алфавите.
9. Продукция (синтаксическое правило) x®h– способ преобразования цепочки вида axb (a, x, b Î(TÈH)*) в цепочку вида ahb (hÎ(TÈH)*).
10. Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.

Лекция №2.

Дата добавления: 2015-12-01