Лекции Русакова (1021002), страница 17
Текст из файла (страница 17)
Такой способ отметоксостояний автомата Мура называется каноническим способом отметок.Если исходные для алгоритма регулярных выражений R1,…, Rpзаданные регулярные события являются многочленами, то они заключаютсяв обычные (неитерационные) скобки. Это условие будет называтьсяусловием правильной записи регулярных выражений.Определение.Местами в правильно записанном регулярном выражении R надалфавитом X = (x1,…,xn) условимся называть специально вводимые знакираздела (вертикальные линии), ставящиеся между любыми двумя знакамиэтого выражения (знаками в выражении R являются буквы алфавита Х,символ пустого слова ε, знак дизъюнкции, итерационные и обычные скобки).Определение.158Кроме этих так называемых разделяющих мест (знаков раздела)вводится еще два места – начальное и конечное. Первое их нихрасполагается слева от самого левого знака выражения R, а второе – справаот самого правого знака.Например, R = z ∨ x {y ∨ z}, где R – регулярное выражение.Приведем это выражение к правильной форме R = (z ∨ x {y ∨ z}).Проведем разметкуИз этого выражения видно, что регулярное выражение R имеет 11 мест.Развернемпоследовательно,данноебукварегулярноевыражениезавыпишембуквой,вслово,какое-либотословоестьизпредставляемого им события.
При этом развертывание, будем осуществлятьпереходя от одного места данного регулярного выражения к другому и отначального места к конечному месту. Такие переходы бывают двух видов –непосредственный переход и переход через букву основного алфавита Х,в котором задается представляемое выражением событие.Например, рассмотрим процессы развертывания размеченного вышевыражения R в принадлежащие представляемому им событию слова z и xyz.Приразвертываниивыражениявпервоесловонеобходимоосуществить непосредственный переход от начального места 1 к месту 2,переход через букву z от места 2 к месту 3 и непосредственный переход от 3к конечному месту 11.При развертывании выражения в слово xyz порядок переходов будетследующий: непосредственный переход от места 1 к месту 4 переход черезбукву x – от 4 к 5, непосредственный переход – от 5 к 6, переход через букву159у – от 6 к 7, непосредственный переход от 7 к 10, непосредственный переходот 10 к 8, переход через букву z – от 8 к 9, непосредственный переход от 9 к10 и непосредственный переход от 10 к 11.Пусть R – регулярное выражение, q = xi1 xi2 … xik произвольное словово входном алфавите события, представляемого выражением R.Условимся, что место α в выражении R связано словом q с местом β втом же выражении, если от места α к месту β можно перейти с помощьючередования любого числа непосредственных переходов и переходов черезбуквы xi1, xi2, …, xik слова q, взятых по одному разу в том порядке, в какомони входят в слово.Это условие означает, что место β q–следует за местом α всякий раз,когда α связано с местом β словом q.Также условимся говорить, что место β подчинено месту α, если отместа α к месту β можно перейти с помощью одних лишь непосредственныхпереходов, т.
е. если место α связано с местом β пустым словом ε.4.16. Правилаподчиненияместврегулярныхвыражениях.1. Начальные места всех термов многочлена, помещенного в обычныеили итерационные скобки, подчинены месту, находящемуся непосредственнослева от открывающей скобки из пары скобок, в которые заключен данныймногочлен (многочлен по этому правилу может вырождаться в одночлен собязательным заключением его в скобки).1602. Место, расположенное непосредственно справа от закрывающей(итерационной или обыкновенной) скобки подчинено конечным местам всехтермов многочлена (в частном случае, одночлена), заключенного всоответствующие скобки, а в случае итерационных скобок – также месту,расположенному непосредственно слева от соответствующей открывающейскобки.3.
Начальные места всех термов многочлена (в частном случае,одночлена), заключенного в итерационные скобки, подчинены месту,расположенному непосредственно справа от соответствующей закрывающейскобки.4. Место, расположенное непосредственно справа от символа пустогослова ε, подчинено месту, расположенному непосредственно слева от этогосимвола.5.
Если место γ подчинено месту β, а место β подчинено месту α, томесто γ подчинено месту α (свойства транзитивности для отношенияподчиненности мест).6. Каждое место подчинено самому себе.В качестве примера использования приведенной системы правилустановим отношение подчиненности мест для рассмотренного вышерегулярного выражения. Место 1 кроме самого себя не подчинено никакимдругим местам. То же самое относится к местам 3, 5, 7, 9.Места 2, 4 кроме самих себя, подчинены месту 1 (по правилу 1).Место 6 и 8 – месту 5 (по правилу 1) и месту 10 (по правилу 3).Место 10 подчинено (кроме самого себя) местам 5,7 и 9 (по правилу 2).Место 11 подчинено (кроме самого себя) местам 3 и 10 (по правилу 2) иместам 5, 7 и 9 (по правилу 5).161Определение.Основными местами в таких выражениях считаются по определениювсе места, непосредственно слева от которых стоит буква основногоалфавита, а также начальное место.Определение.Все места, непосредственно справа от которых стоит буква основногоалфавита, называются предосновными.4.17.
Правилапостроенияосновногоалгоритмасинтеза конечных автоматов.1. Заданные регулярные события (число которых предполагаетсяконечным)представляютсяправильнозаписаннымирегулярнымивыражениями R1,…,Rp. Все места (как основные, так и не основные) в этихвыражениях обозначаются вертикальными черточками (линиями).2. Каждому основному месту в выражениях R1,…,Rp приписывается вкачестве индекса неотрицательное целое число.
При этом всем начальнымместам приписывается один и тот же индекс (нуль). Что же касаетсяостальных основных мест, то они нумеруются в произвольном порядкенатуральными числами 1, 2, …Все введенные здесь индексы называются основными. Основныеиндексы подписываются под вертикальными чертами соответствующих им(основных) мест и подчеркиваются снизу общей для каждого из выраженийR1,…,Rp горизонтальной разделительной чертой.3.
Индекс (основной) каждого основного места α распространяется вкачестве неосновного индекса на все места (как основные, так и неосновные),подчиненные месту α, но отличные от него самого.162При этом каждое место β получает некоторое множество неосновныхиндексов. Все индексы этого множества подписываются в произвольномпорядке под вертикальной чертой, соответствующей месту β, нижеразделительной горизонтальной черты. Все индексы (как основные, так инеосновные), относящиеся к любому предосновному месту, заключаются вобщую рамку.4. Строится таблица переходов некоторого автомата Мура. В качествесостояний этого автомата берутся подмножества множества всех основныхиндексов.При этом подмножество, состоящее из основных индексов i1,…, ik(k≥1), будем обозначать через i1∨i2∨…∨ik, а пустое множество основныхиндексов – звездочкой (соответствующее ему состояние автомата Аназывается пустым).Построение таблицы переходов с состояниями автомата Мура Аначинается с вписывания обозначений строк и столбцов таблицы.Строки таблицы обозначаются (в произвольном порядке) различнымибуквами входного алфавита заданного множества событий.Столбцы обозначаются состояниями автомата А, начиная с нулевого.Последующий столбец обозначается в произвольном порядке состоянием изпредыдущего столбца после вписывания всех состояний в этот столбец.На пересечении произвольной (xi-й) строки и произвольного (qj-го)столбца таблицы вписываются состояния (множества основных индексов),состоящие из основных индексов всех тех и только тех основных мест,которые xi-следуют за предосновными местами, в числе индексов которых(как основных, так и не основных) находится хотя бы один индекс,принадлежащий состоянию qj.
В случае отсутствия основных мест стребуемыми свойствами на соответствующем месте таблицы вписываетсяпустое состояние.1635. Каждое из состояний i1∨i2∨…∨ik (k≥1), обозначающее столбцытаблицы переходов, отмечается множеством (Rj1, …, Rjm) всех символов тех итолько тех регулярных выражений R1,…,Rp, конечные места которыхсодержат в числе своих индексов (как основных, так не основных) хотя быодин из индексов i1,…,ik.Пустоесостояниеотмечаетсяпустыммножествомрегулярныхвыражений R1,…,Rp и обозначается через ( ). С помощью введенных отметок,принимаемых за выходной алфавит, строится отмеченная таблица переходовискомого конечного автомата Мура.6.ВслучаенеобходимостинайденныйавтоматМураАинтерпретируется как автомат Мили В.
Таблица переходов автомата А приэтом принимается за таблицу переходов В. Таблица выходов автомата Вполучается в результате подстановки в его таблицу переходов вместосимволов состояний символов, соответствующих состояниям выходныхсигналов (отметок) автомата А.Построенные автоматы А и В представляют заданные событиямножествами своих состояний и (с точностью до пустого слова)множествами своих выходных сигналов.Событие,заданноерегулярнымвыражениемR,представляетсямножеством всех тех и только тех состояний, которые отмеченымножествами, содержащими в качестве своих элементов выражение Ri. Этоже событие (за вычетом лишь пустого слова, если оно содержится в событии)представляется в автоматах А и В множеством всех тех и только техвыходных сигналов (множеств), состоящих из выражений R1,…,Rp, которыесодержат в своем составе выражение Ri(i = 1,..., p). Множество состояний,отмеченных пустым множеством ( ), или выходной сигнал ( ) представляетсобытие, состоящее из всех слов входного алфавита, не вошедших взаданные события.164В процессе синтеза автомата или по окончании этого процессапроизводят переобозначения состояний и выходных сигналов с цельюупрощениязаписитаблицпереходовивыходов.Обычноприпереобозначении состояний их просто нумеруют натуральными числами1, 2, ..., используя для обозначения начального состояния единицу.
Внекоторых случаях оказывается целесообразным обозначать состояниячислами 0, 1, 2, ..., тогда начальное состояние обозначается всегда нулем.Пример.Рассмотрим пример синтеза конечного автомата в соответствии сописанным алгоритмом.Пусть требуется построить конечный автомат, в котором для входногоалфавита Х, состоящего из двух букв х и у, были бы представлены двасобытия: событие R1, состоящее из всех слов в алфавите Х, в которых всебуквы х предшествуют всем буквам у, и событие R2, состоящее из всех слов валфавите Х, которые кончаются буквой х.Применяя правило 1, записываем заданные события в виде следующихрегулярных выражений:После разметки мест эти выражения приобретут вид:Применяем правило 2, в результате получим выражения:В результате применения правила 3 получаем:165Применение правила 4 приводит к построению таблицы переходов 4.1.Применение правила 5 дает отмеченную таблицу переходов 4.2.Обозначая выходные сигналы ( ), (R1), (R2), (R1, R2) соответственночерез z, u, v и w и, нумеруя состояния, переходим к отмеченной таблицепереходов 4.3.При интерпретации построенного автомата как автомата Мили всоответствии с правилом 6 мы получим таблицу его выходов 4.4.Построенные автоматы представляют событие R1 состояниями 1, 2, 3, асобытие R2 – состояниями 2, 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
