КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Автомат Мура
Определение автомата Мили.
Определение:Конечным автоматом называется набор из 5 объектов , где: - входной алфавит; выходной алфавит; множество внутренних состояний; функция перехода (в следующее состояние); функция выхода. Таким образом, конечный автомат описывается тремя множествами и двумя функциями. Обе функции зависят от текущего внутреннего состояния и от входного символа, считываемого в данный момент времени. Автомат действует следующим образом. Конечный автомат, находящийся во внутреннем состоянии , считывает входной символ . Функция принимает на паре значение - первый символ выхода. Функция принимает на паре значение , которое является следующим внутренним состоянием. Пусть входящие символы записаны на входной ленте: **********. Автомат считывает с нее символы один за другим. По прочтению каждого символа автомат печатает выходной символ на выходной ленте и переходит в новое внутреннее состояние. В определении подразумевается, что функции и в описании автомата М всюду определены, т.е. каждая пара из прямого произведения задает их значения. Такое описание автомата является полным, т.е. если задано начальное состояние автомата, то он способен считывать любую последовательность входных символов и выдавать однозначно определенную цепочку символов на выходе. Конечный автомат считается заданным, если заданы множества (конечные), а также даны функции или приведено их описание. Существует три способа задания конечных автоматов: таблица, диаграмма и матрица переходов. Пример 1. Конечный автомат задан следующим образом: , , , . Значения функций заданы таблицей:
Пусть на входе дана двоичная последовательность 0101 и автомат находится в состоянии , тогда на выходе получаем последовательность: 0010. Этот автомат можно наглядно представить в виде диаграммы, которая, по сути, является ориентированным графом.
Вершины этого графа помечены символами, обозначающими внутреннее состояние. Каждая дуга помечено парой символов (метка) , где - входной символ, вызывающий переход в следующее состояние, а - символ на выходе. Второй способ описания автомата – таблица состояний. Этот способ часто приводится в виде условия задачи. Это просто табличное представление функций и :
Таблица удобнее для вычислений, диаграмма - нагляднее. Например, по диаграмме легко обнаружить состояния, не достижимые из других состояний. Кроме того, автомат можно задать с помощью матрицы. Такая матрица всегда будет квадратной по форме, а размерность её зависит от количества внутренних состояний. Каждая позиция матрицы отвечает за определённый переход из одного состояния в другое. Если какой-то переход существует, то на определённом месте матрицы должна стоять соответствующая метка. Если же некоторый переход отсутствует, то на этом месте в матрице стоит ноль. Пример 2. По приведенному описанию построить конечный автомат. Задать его таблицей и диаграммой. Данный автомат проверяет четность числа считываемых единиц на входе из последовательности нулей и единиц, и выводит на печать символы чёт и нечёт в ответ на запрос, которому соответствует входной символ Q. Согласно условию, алфавит на входе: , алфавит на выходе состоит из символов: . Множество внутренних состояний: , где содержание этих состояний следующее: - считано четное число единиц; - считано нечетное число единиц. Анализируя работу автомата, можно составить таблицу:
Считав символ Q, автомат печатает "чет", если число ранее считанных единиц было четно, и "нечет" - если нечетно. Например, входная последовательность символов имела вид: 0110Q1110Q. Она будет переработана в последовательность: 0110четн1110нечет. Диаграмма для данного автомата может быть составлена с помощью построенной таблицы:
Любой конечный автомат Мили может быть преобразован в автомат, в котором выходной символ является функцией только состояния в настоящий момент. Для этого полагают - новый алфавит, , . Отсюда получаем выражение для : или . Такой автомат называется автоматом Мура. Так как автоматы Мили и Мура можно преобразовать друг в друга, то обычно достаточно рассматривать автомат Мили, тем более что число состояний у него меньше, чем у соответствующего автомата Мура.
Дата добавления: 2014-01-03; Просмотров: 4313; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |