Типы автоматов и способы их задания 11. Вероятностные автоматы 11.1. Особенности вероятностных автоматованее рассматривались детерминированные автоматы, в которых из любого состояния возможен переход только в одно из следующих состояний. Такая модель реализуется в большинстве реальных цифровых схем. В теории автоматов изучаются также более сложные модели, например вероятностные (недетерминированные или стохастические) автоматы. Вероятностные автоматы отличаются тем, что в них переходы из одного состояния в другое происходят случайным образом, т.е. входной сигнал может вызывать переход из текущего состояния в различные состояния с некоторой вероятностью. Вероятностный автомат может быть задан в виде графа или таблицы переходов, которая принимает вид матрицы переходных вероятностей. Задание алгоритма работы вероятностного автомата рассмотрим на примере автомата управления светофором (АУС) на перекрестке улиц с различной интенсивностью движения. Этот автомат преимущественно пропускает транспорт по улице с интенсивным движением (магистрали) и не перекрывает ее при появлении на поперечной улице каждой отдельной машины. Естественно, что численные значения вероятностей переключения светофора и длительность его сигналов выбираются исходя из реальных условий. Схема такого перекрестка может быть представлена в виде рисунка 11.1.На перекрестке установлены светофоры (С) и датчики (Д) наличия транспорта на поперечной улице. Сигналы от датчиков являются входными сигналами для автомата. Выходным сигналом автомата является сигнал управления светофором. Для простоты будем считать, что автомат имеет только два состояния: проезд по магистрали открыт (Q0 )или закрыт (Q1). Очевидно, что при открытом движении по магистрали движение по поперечной улице запрещено и наоборот. Входным сигналом является сигнал от датчика наличия транспорта на поперечной улице. Граф автомата в этом случае может быть представлен в виде рис. 11.2. х; р01х; р11 х; р10 Q1 Q0х; р00Рис. 11.2На рис. 11.2 приняты следующие обозначения: х – входной сигнал (х=1, если на поперечной улице есть транспорт); рij – вероятность (переходная) перехода из состояния i в состояние j; Q0 – начальное состояние (проезд по магистрали открыт). На рис.11.2 видно, что из вершин графа вероятностного автомата могут выходить несколько дуг, отмеченных одинаковым входным сигналом. Вариант графа для конкретных значений переходных вероятностей приведен на рис. 11.3. х; 0,3 х; 0,5 х; 1 х; 0,5Q1 Q0х; 0,7 х; 1Рис. 11.3Таблица переходов вероятностного автомата имеет вид матрицы переходных вероятностей и составляется для каждого входного сигнала (рис.1.4) х=1 Р0 Р1 Р0 0,7 0,5 Р1 0,3 0,5 х=0 Р0 Р1 Р0 1 1 Р1 0 0 Рис. 11.4Вероятностный автомат может быть реализован в виде системы, состоящей из детерминированного автомата и датчика случайных чисел, который выдает сигналы с заданным распределением вероятностей. Для автомата реализующего граф рис. 11.3, достаточно использовать датчик, формирующий числа, равномерно распределенные в интервале от 0 до 1. В зависимости от состояния и входного сигнала случайное число сравнивается с пороговым значением (в данном случае это величины 0,3 или 0,5). Сигнал с выхода схемы сравнения поступает на дополнительный вход автомата вместе с основным сигналом от датчика наличия транспорта. Тем самым реализуется вероятностная логика работы автомата. Для большего приближения к реальности граф рис. 11.3 можно дополнить состояниями Q2 иQ3, соответствующими желтому сигналу светофора. В этом случае граф принимает вид, приведенный на рис. 11.5.Матрицы переходных вероятностей показаны на рис.11.6. х=0 р0 р1 р2 р3 р0 1 0 0 0 р1 0 0 0 1 р2 0 0 0 0 р3 0 0 0 0 х=1 р0 р1 р2 р3 р0 0,7 0 0,3 0 р1 0 0,5 0 0,5 р2 0 1 0 0 р3 1 0 0 0 Рис.11.6На рис.11.6 видно, что сумма вероятностей переходов в любом состоянии равна 1 или 0 (если состояние недостижимо при данном входном сигнале).^ В заключение приведем определение недетерминированного автомата. Конечным недетерминированным распознающим автоматом называют совокупность (X, Q, Ф), где: 1) Х – конечное множество символов входного алфавита; 2) Q - конечное множество состояний автомата, удовлетворяющее условиям: а) во множестве Q выделено непустое подмножество начальных состояний Q0È Q; б) множество Q разбито на два непересекающихся класса – допускающие и недопускающие состояния. 3) Ф- функция переходов: Ф: Q х ® р(Q); Ф: (q, x) ® Qx È Q, которая каждой паре (q, x) из состояния q и входного сигнала х ставит в соответствие некоторое подмножество Qx из множества всех состояний Q. ^ 11.2. Вероятностные автоматы с -переходами. В теории часто рассматривается автоматы, называемые автоматами с -пере-ходами (с эпсилон - переходами). Эпсилон-переходом называется переход между состояниями, который может быть выполнен без входного сигнала. Такие переходы обозначаются символом . Использование эпсилон-переходов позволяет просто объединять несколько автоматов в один. Пусть требуется построить граф автомата, который должен распознавать двоичные, десятичные и шестнадцатеричные числа в стандартном формате ассемблера. Автомат должен распознавать строки, удовлетворяющие одному из следующих условий: строка состоит из одной или более цифр (0 – 9) и может заканчиваться символом «D» (например «1367» или «2345D»); строка состоит из одного или более символов «0» или «1» и заканчивается символом «B» (например «01011B»); строка состоит из одной или более десятичной цифр или символов от « А » до «F» и заканчивается символом «H» (например «9AD4H»). Граф такого автомата представлен на рис.11.7. В теории автоматов доказывается, что любой вероятностный автомат может быть заменен эквивалентным детерминированным (обычным) автоматом. Вероятностные автоматы используются в тех случаях, когда схема вероятностного автомата проще, чем схема эквивалентного детерминированного автомата. Вероятностные автоматы могут применяться при моделировании умственной деятельности человека, например при машинном переводе с одного языка на другой, в частности, при разработке трансляторов. Граф эквивалентного детерминированного автомата имеет меньше состояний, но более сложную систему переходов.Контрольные вопросыПоясните особенности вероятностных автоматов. Как отмечаются дуги вероятностного автомата? Как составляются матрицы переходных вероятностей? Дайте определение конечного недетерминированного распознающего автомата. Что такое -переход? Для чего используют -переход? Какая информация содержится в матрице переходных вероятностей? Приведите пример вероятностного автомата.