нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
 Скачать 0.65 Mb.
|
2. ОСНОВЫ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ2.1. Понятие конечного автомата2.1.1. Общие сведения о конечных автоматахДанный раздел посвящен математическому описанию работы цифровых вычислительных машин (ЦВМ) с помощью понятий множества, отношения, функции и графа. При этом из рассмотрения исключаются аналоговые вычислительные машины, состояние которых меняется непрерывно. Не рассматриваются также гибридные устройства, сочетающие цифровые и аналоговые компоненты. С математической точки зрения, все многообразие ЦВМ можно отнести к одному классу конечных автоматов. Они обладают следующими свойствами: Любая ЦВМ состоит из конечного числа элементов, каждый из которых в любой момент времени может находиться лишь в одном из конечного числа устойчивых состояний. Поэтому вся машина в целом имеет конечное множество состояний. Любая ЦВМ работает последовательно, то есть ее операции синхронизированы сигналами тщательно настроенных электронных часов. В связи с этим состояние машины меняется в четкой последовательности. ЦВМ является детерминированным устройством. Это значит, что при наличии полной информации о внутренних состояниях всех элементов машины и всех ее входов следующее состояние машины определяется однозначно. ЦВМ делятся на универсальные и специализированные. В теории конечных автоматов анализируются универсальные машины, которые используются для любых целей. С функциональной точки зрения современные ЦВМ состоят из 5 типов устройств: 1) устройство ввода; 2) устройство памяти; 3) арифметико-логическое устройство; 4) устройство управления; 5) устройство вывода. ЦВМ конструируются на электронных схемах, имеющих два устойчивых состояния. Основная причина – технологическая. Но в этом случае возрастает также надежность электронных схем. Это связано с тем, что небольшие отклонения характеристик электронных схем не отражаются на работе всего устройства в целом. Таким образом, типичный сигнал в элементах ЦВМ имеет следующий вид Рис. 2 При этом единицей кодируется сигнал более высокого уровня, а нулём – более низкого. Или более точно, устанавливается некоторое пороговое значение сигнала и далее сигналы выше порога кодируются 1, а ниже – 0. Таким образом, не вникая в дальнейшие особенности работы электронных схем, отметим, что сигналы в таких устройствах двузначны. Это значит, что переменные, используемые для их описания, принимают только два значения. Это же замечания относится и к материальным носителям информации и к преобразователям сигналов. В результате состояние любой ЦВМ, имеющей конечное число r двоичных элементов математически может быть описано следующим образом. Нумеруются элементы ЭВМ, затем с каждым устойчивым состоянием связывается вектор . При этом координате приписывается значение 1, если -й элемент находится в единичном состоянии, и 0, если -й элемент находится в нулевом состоянии. 2.1.2. Абстрактное определение конечного автоматаАбстрактным описанием ЦВМ служит математическое понятие конечного автомата. Определение. Конечным автоматом называется набор из пяти объектов: , где - конечный список входных символов (входной алфавит); - список выходных символов (выходной алфавит); - множество внутренних состояний; - функция перехода в следующее состояние; - функция выхода. Таким образом, конечный автомат математически описывается тремя множествами и двумя функциями. Его действие состоит в том, что он считывает последовательность входных символов (программу), а затем печатает последовательность выходных символов. Это действие происходит последовательно, а именно, конечный автомат, находящийся во внутреннем состоянии считывает входной символ . Функция на паре принимает значение , которое печатается в качестве выходного символа. Функция на той же паре принимает значение , которое является следующим внутренним значением автомата. Далее автомат считывает новый входной символ, печатает выходной, переходит в следующее состояние и так далее. Эту последовательность работы можно наглядно представить в следующем виде. Рис. 3 В определении конечного автомата предполагается, что функции и всюду определены. Такое описание автомата называется полным. Пример. Автомат имеет входной алфавит , выходной алфавит , множество внутренних состояний .Функции перехода и выхода задаются предписаниями: Таблица 5
Подадим на вход последовательность 0,1,0,1. Если автомат находился в состоянии , то считав первый символ 0, он перейдёт в состояние и напечатает 0. Считав затем 1, он перейдёт в состояние и напечатает 0. Считав следующий 0, он перейдёт в состояние и напечатает 1. Наконец, считав последний символ 1, автомат закончит работу в состоянии , печатая 0. Таким образом, автомат преобразовал входной сигнал 0101 в сигнал 0010 на выходе. Возможны следующие способы описания конечного автомата: С помощью диаграммы состояний, которая представляет собой ориентированный граф. Вершины этого графа помечаются символами, обозначающими внутренние состояния автомата. А каждая дуга помечается упорядоченной парой символов . Первый символ есть входной символ, вызывающий переход автомата в следующее состояние. Второй символ - выходной символ, который автомат печатает. Диаграмма состояния для выше приведённого примера имеет вид. Рис. 4 2) Второй способ описания конечного автомата – таблица состояний – это табличное представление функций и . В соответствии с примером Таблица 6
Оба способа описания конечного автомата имеют свои преимущества и недостатки. Таблица состояний удобна при вычислениях, а диаграмма состояний является более наглядной. В частности, по диаграмме состояний конечного автомата можно обнаружить состояния недостижимые из других состояний. Например: Рис. 5 На этом рисунке показана диаграмма состояний конечного автомата, у которого состояние недостижимо, если автомат начинает работу из состояний или . | ||||||||||||||||||||||||||