Раздел дискретной математики, изучающий абстрактные автоматы: вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. Работа распознавателя. Функциональная схема абстрактного автомата, порядок работы с ним.
Аннотация к работе
Государственное образовательное учреждение высшего профессионального образования Сибирский Государственный аэрокосмический университет имени академика М.Ф. Реферат по дисциплине "Теория систем" на тему: "Теория автоматов"Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.Абстрактная теория автоматов рассматривает структуру без привязки к средствам технической реализации.Существует класс грамматик, которому соответствует свой класс распознавателей, определяющий тот же класс языков: - язык L праволинейный тогда и только тогда, когда он определяется односторонним детерминированным конечным автоматом; язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью; язык L контекстно зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным автоматом с магазинной памятью; язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга (этот вид математических объектов рассматривается в курсе "Математическая логика и теория алгоритмов"). Такой распознаватель включает в себя входную ленту, читающую головку и устройство управления, в соответствии с рисунком 1.Основной задачей распознавателя является определение того, принадлежит ли заданная строка языку, соответствующему распознавателю.Абстрактный автомат - математический объект, представляющий собой совокупность элементов: A=(S,X,Y,?,?), где S - конечное множество состояний автомата; X,Y - конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом; ?:SXY->S - переходное отношение (переходная функция); ? - выходная функция. Абстрактный автомат имеет следующую функциональную схему, в соответствии с рисунком 2. Порядок работы абстрактного автомата следующий: - при поступлении очередного символа на вход автомата переходная функция ? на основании поступившего символа xi и текущего состояния si определяет новое состояние автомата Si 1; выходная функция на основе текущего состояния автомата si и текущего входного символа xi определяет текущий выходной символ.По характеру отсчета дискретного времени автоматы делятся на синхронные и асинхронные. В синхронных конечных автоматах моменты времени, в которые автомат считывает входные сигналы, принудительно определяются синхронизирующими сигналами. После очередного синхронизирующего сигнала с учетом считанного сигнала и в соответствии с соотношениями для функционирования автомата происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Асинхронный конечный автомат считывает входной сигнал непрерывно, а реагируя на достаточно длинный входной сигнал постоянной величины X, он может, как это следует из соотношений для функционирования автомата, несколько раз изменять свое состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое состояние, которое уже не может быть изменено данным входным сигналом. Также задан набор условных вероятностей того, что вероятностный автомат, находясь в состоянии aj и получив входной сигнал x, перейдет в состояние ai, и выдаст сигнал y.В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления, т.е. информация представлена в виде комбинации нулей и единиц. При этом поступление на входы некоторой последовательности входных сигналов, состоящих из нулей и единиц, вызывает появление на выходах вполне определенной последовательности выходных сигналов, также состоящей из нулей и единиц. Выходные сигналы в схемах второго класса определяются не только значениями входных сигналов в данный момент времени, но и состояниями схемы, которые в свою очередь зависят от значении сигналов, поданных на ее входы во все предшествующие моменты времени.Среди систем элементов, выпускаемых промышленностью, наибольшее распространение получили логические элементы, реализующие операции: И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, а так же элементы булевого базиса.В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Автомат - дискретный преобразователь информации способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени. A = {a0,a1,a2,...