![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Тема 3. Элементы теории конечных автоматов
Основные определения теории конечных автоматов Конечным автоматом (просто автоматом) называется система (пятерка) : S = <X , Y , Z , φ, ψ>, где X = {х1, х2, …, хi} — конечное входное множество (входной алфавит); Y = {y 1, y 2, …, yj} — конечное множество внутренних состояний автомата (алфавит состояний); Z = {z 1, z 2, …, zk} — конечное выходное множество (выходной алфавит); φ — функция переходов (из состояния в другие состояния); ψ — функция выходов. Если указанные множества бесконечные, то это уже не конечный автомат. Если функция переходов вероятностная, то это недетерминированный автомат. Если в автомате выделено одно состояние, называемое начальным (обычно это y 1), то полученный автомат называется инициальным и обозначается <S , y >. Таким образом, по неинициальному автомату с i состояниями можно i различными способами определить инициальный автомат. Функция переходов представляет собой отображение вида φ: X × X ↦ Y или в другом виде: y (t + 1) = φ[x (t ), y (t )], где x (t ), y (t ), y (t + l ) — конкретные символы алфавитов X и Y соответственно в моменты автоматного времени t , t + 1 (в тактах t и t + 1); y (t ) — текущее внутреннее состояние при соответствующем x (t ); y (t + l ) — последующее внутреннее состояние. Иначе говоря, функция переходов определяет последующее состояние автомата по заданному текущему и входному символу. Функция выходов представляет собой отображение вида ψ: X × Y ↦ Z или в другом виде: z (t ) = ψ[x (t ), y (t )], где x (t ), y (t ), z (t ) — конкретные символы алфавитов X , Y , Z соответственно. Мы не будем особо выделять последующие значения x (t + 1) и z (t + 1), поэтому зависимость от t будем указывать только для внутреннего состояния, чтобы отделять y (t ) от y (t + l ). Указанная функция выходов — функция так называемого автомата Мили . В теории конечных автоматов рассматривается также автомат Мура , у которого функция выходов проще: ψ: X ↦ Y или z (t ) = ψ[y (t )]. Автомат называется комбинационным , если для любого входного символа х и любых состояний уi, yj φ(х, уi) = φ(х, уj) = z , иначе говоря, если выходной символ z не зависит от состояния и определяется текущим входным символом. Говорят, что у такого частного класса автомата все состояния эквивалентны и, следовательно, комбинационный автомат имеет одно состояние. Такой автомат задается тройкой символов: S = <X , Z , ψ>. Рассмотрим представление конечного автомата (КА) в виде «черного ящика» (рис. 51). Рис. 51. Конечный автомат в виде «черного ящика» В комбинационном автомате внутренних состояний не указывают. Входное слово — последовательность входных символов. Выходное слово — последовательность выходных символов, соответствующих входному слову. В конечном автомате также выделяется последовательность символов внутренних состояний, соответствующих входному слову. Большой вклад в теорию дискретных (цифровых) автоматов внесли отечественные ученые: М.А. Гаврилов, который опубликовал первую в мире монографию «Теория релейно-контактных схем» (1950 г.), В.М. Глушков, В.Н. Рогинский, П.П. Пархоменко, В.Г. Лазарев, С.И. Баранов, А.Д. Закревский, Э.А. Якубайтис, С.В. Яблонский, В.И. Варшавский и др. Описание конечных детерминированных автоматов Поскольку функции φ и ψ определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводят в одну, φ × ψ: X × Y ↦ Y × Z и называют таблицей переходов-выходов, или просто таблицей переходов (автоматной таблицей). При задании автомата ориентированным графом (орграфом) его вершины сопоставляют с внутренними состояниями, а дуги — с условиями перехода из состояния в состояние. Дуги помечают входными символами автомата, а также соответствующими выходными символами, если это автомат Мили. Рассмотрим граф переходов некоторого автомата Мили (рис. 52), X = {х1, х2}, Y = {у1, у2, y 3}, Z = {z 1, z 2, z 3}. На графе автомата Мили (рис. 52) дуги помечаются дробью, где в числителе — входной символ, а в знаменателе — выходной символ. Рис. 52. Граф некоторого автомата Мили Представим этот же автомат Мили таблицей переходов (табл. 51). Таблица 51 Таблица переходов выходов автомата Мили, В клетках табл. 51 записывается дробь, в числителе которой указывается последующее внутреннее состояние y (t + l ), а в знаменателе — выходной символ z (t ). Это указано в специальной выноске таблицы Рассмотрим граф некоторого автомата Мура (рис. 53), X = {х1, х2}, Y = {у1, у2, y 3}, Z = {z 1, z 2, z 3}:
Рис. 53. Граф некоторого автомата Мура Выходные символы в автомате Мура сопоставляются с конкретными внутренними состояниями и записываются в знаменателе дроби, помечающей внутренние состояния. Само внутреннее состояние указывается в числителе. Дуги графа автомата Мура помечаются только входными символами. Соответствующая этому автомату Мура таблица переходов представлена табл. 52. Таблица 52 Таблица переходов выходов автомата Мура, В клетках табл. 52, соответствующих входным символам, записывается только последующее внутреннее состояние y (t + l ), что указано в специальной сноске (y (t + l )). Комбинационный автомат задается таблицей истинности (соответствия), уже известной нам, так как граф переходов такого автомата имеет одну вершину и m петель, где m — число входных символов. Пример таблицы истинности, задающей некоторый комбинационный автомат, приведен в табл. 53. Таблица 53 Таблица истинности комбинационного автомата: X ={х1, х2, х3,х4}, Z = { z 1, z 2, z 3, z 4} В отличие от комбинационного конечного автомата, имеющего одно внутреннее состояние, конечные автоматы, имеющие больше, чем одно внутреннее состояние, называются последовательностными конечными автоматами , или просто последователъностными автоматами . Рассмотрим последовательностный автомат, заданный табл. 54. Зафиксируем начальное состояние y 1и каждому входному слову (последовательности входных символов) Это соответствие, отображающее входные слова в выходные, называется автоматным отображением . Таблица 54 Таблица переходов-выходов некоторого автомата Мили Зададим входное слово а = x1х2х3х4. Тогда выходное слово ω = z 1z 1z 1z 3. Рассмотрим подробнее процесс формирования выходного слова: В этой последовательности указаны так называемые переходы из состояния в состояние, обведенные линией. Например, при поступлении х2автомат сначала находится в состоянии y1, а затем переходит в состояние у2. Указанные выше последовательности иногда изображают стрелками в таблице переходов-выходов. Состояния yjназывают достижимыми из состояния yi, если существует входное слово α, такое, что φ(α, yi) = yj. Состояния называются эквивалентными , если они соответствуют одинаковым последовательностям «входное слово — выходное слово»; причем длина такой последовательности может быть любая ≥ 1. Автомат называется сильно связанным , если из любого его состояния достижимо любое другое состояние. Автомат называется автономным , если его входной алфавит состоит из одной буквы X = {х}. Все входные слова автономного автомата имеют вид хх…х. Рекомендуемые страницы:
Читайте также:
|
Последнее изменение этой страницы: 2016-03-16; Просмотров: 2065; Нарушение авторского права страницы