Загрузка...

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ


«В начале было слово…»
Бытие, 1,1

Определение. ТЕОРИЯ АВТОМАТОВ – это раздел дискретной математики, изучающей математические модели дискретных преобразователей информации.
Произвольный автомат будем представлять как математическую (формальную) систему, имеющую входные и выходные каналы данных и находящийся в каждый из дискретных моментов времени в одном из конечного числа состояний.
Зададим следующие множества:

— множество входных знаков (входной алфавит),

— множество выходных знаков (выходной алфавит),

— множество состояний автомата.

Особенность этих множеств состоит в том, что они содержат конечное число элементов.
Тогда автомат можно представить в следующем виде:

Особенностью автоматов является то, что они функционируют во времени.
Работу любого автомата можно проиллюстрировать с помощью временных диаграмм.

ВРЕМЕННАЯ ДИАГРАММ РАБОТЫ АВТОМАТА.

Изначально состояние автомата неизвестно, но, подавая на вход автомата сообщение в виде последовательности знаков входного алфавита, можно понять в каком состоянии находился автомат по выходным данным, снимаемым с выхода автомата.

ПОДХОДЫ К ОПРЕДЕЛЕНИЮ И ИЗУЧЕНИЮ АВТОМАТОВ.

1 подход. МАКРОПОДХОД При макроподходе изучают внешнее поведение автомата, то есть то, как автомат перерабатывает входные данные и в каких состояниях находиться, абстрагируясь от внутренней структуры автомата.
Такие автоматы называются – АБСТРАКТНЫМИ АВТОМАТАМИ.

2 подход. МИКРОПОДХОД При микроподходе учитывается структура автомата, его составные части, их функционирование и связь между собой.
Такие автоматы называются – СТРУКТУРНЫМИ АВТОМАТАМИ.

3 подход. ПРАКТИЧЕСКИЙ или  ПРАКТИЧЕСКИЙ АСПЕКТ При практическом подходе учитывается не только внешнее поведение элементарных (абстрактных) автоматов, но и особенности их реализации в виде материальных объектов (дискретных устройств).

Загрузка...