Лекции по дискретке (1021001), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Вторая операция применяется только к выравниванию алфавитных отображений φ, т. е. к таким отображениям у которых длины входных и соответствующих им выходных слов равны между собой. Сущность этой операции – операции пополнения отображения φ, заключается в распространении отображения φ на начальные отрезки слов.

Если s – произвольный начальный отрезок любого слова р из области определения отображения φ, то полагаем φ(s) равным начальному отрезку слова φ(p), т. е. имеющему длину s.

В результате применения операции пополнения к произвольному выровненному алфавитному отображению φ возникает новое отображение φ₁ область определения которого удовлетворяет условию полноты. Условимся называть это отображение пополнением отображения φ.

Если пополнение φ₁ отображения φ является однозначным, то очевидно, что оно удовлетворяет всем четырем условиям автоматности.

42.Представление событий в автоматах.

Основной задачей абстрактной теории автоматов является установление связей, существующих между автоматами и индуцируемыми ими отображениями.

Определение.

Произвольное автоматное отображение можно задавать событиями, которые соответствуют этим отображениям.

Определение.

Для произвольного автомата А множество S_y всех входных слов, вызывающих появление выходных слов, которые оканчиваются одной и той же буквой (выходным сигналом) у, называется событием, представленным в автомате А выходным сигналом у. Множество, состоящее из событий S_у, для всех букв выходного алфавита автомата А, называется каноническим множеством событий данного автомата А.

Определение.

Каноническое множество событий любого автомата является автоматным множеством событий.

Очевидно и обратное, что для любого автоматного множества событий M существует такой автомат (в качестве которого можно выбрать как автомат Мили, так и автомат Мура), каноническое множество событий которого совпадает с множеством M.

Определение.

В отличие от автоматного отображения абстрактный автомат не определяется однозначно соответствующим ему каноническим множеством событий, поскольку одно и то же автоматное отображение может индуцироваться различными автоматами.

Важные задачи абстрактной теории автоматов:

1. Задача нахождения по заданному абстрактному автомату А соответствующего ему канонического множества событий – каноническая задача анализа абстрактного автомата;

2. Обратная задача, по заданному автоматному множеству событий M находить абстрактный автомат, каноническое множество событий которое совпадает с M – каноническая задача синтеза абстрактного автомата.

43.Регулярные языки и конечные автоматы.

Определение.

Любое автоматное отображение φ может быть задано конечным множеством М событий во входном алфавите этого отображения.

Если область определения отображения φ конечна, то все события множества М конечны. Конечное событие можно задать, перечислив все его элементы. Ясно, что в случае, когда область определения отображения φ бесконечна, хотя бы одно из событий множества М также будет бесконечным. Поэтому необходимо разработать специальный язык, который позволял бы представлять (описывать) бесконечные события, соответствующими конечными выражениями.

Для языка регулярных выражений алгебры событий используются три операции над событиями:

1) А∪В – объединение (дизъюнкция);

2) А⋅В – умножение (конкатенация);

3) {A} – итерация (обозначается также А*).

Определим конечные множества входных букв Х = {x₁, ..., x_n} и зададим для этого множества регулярное выражение.

Определение.

Регулярным выражением в алфавите Х называется выражение, построенное из букв алфавита Х и из символов операций объединения, умножения и итерации с использованием соответствующим образом круглых скобок.

Всякое регулярное выражение определяет некоторое событие S (событие S получается в результате выполнения всех операций, входящих в регулярное выражение). События, определяемые таким образом, называются регулярными событиями над алфавитом Х. Другими словами регулярным событием (или языком) называется событие, полученное из элементарных событий (однобуквенных слов x_i) применением конечного числа раз операций дизъюнкции, конкатенации и итерации.

Например, в алфавите из трех букв x, y, z регулярное выражение

x {x ∨ y ∨ z} (y ∨ z) задает регулярное событие, состоящее из всех слов, которые начинаются буквой х и заканчиваются буквой y или z. Для конечных автоматов характерны только регулярные события.

Определение.

Общая задача анализа абстрактного автомата ставится как задача нахождения по заданному абстрактному автомату такого события, которое представлено любым множеством его состояний.

Определение.

Общая задача синтеза абстрактного автомата ставится как задача построения по любому конечному множеству событий такого автомата, который представляет каждое событие этого множества некоторым множеством своих выходных сигналов

44.Основной алгоритм синтеза конечных автоматов.

Определение.

Основной алгоритм синтеза конечных автоматов это алгоритм, который позволяет по любому конечному множеству М регулярных событий, заданных своими регулярными выражениями, находить таблицу переходов и выходов конечного вполне определенного автомата Мили и отмеченную таблицу переходов конечного вполне определенного автомата Мура. Таких, что все события множества M представляются как в автомате Мили, так и в автомате Мура некоторыми множествами их выходных сигналов.

Перейдем от представления событий R₁,...,R_p в автомате Мура множествами состояний к представлению их множествами выходных сигналов. Для этого достаточно в качестве выходных сигналов взять различные подмножества заданного множества событий (R₁,…,R_p) и отмечать каждое состояние q автомата множеством тех событий, которые содержат слова, переводящие автомат из начального состояния в состояние q.

Если состояния, не представляют ни одного из заданных событий, то они отмечаются пустым множеством событий. Такой способ отметок состояний автомата Мура называется каноническим способом отметок.

Если исходные для алгоритма регулярных выражений R₁,…, R_p заданные регулярные события являются многочленами, то они заключаются в обычные (неитерационные) скобки. Это условие будет называться условием правильной записи регулярных выражений.

Определение.

Местами в правильно записанном регулярном выражении R над алфавитом X = (x₁,…,x_n) условимся называть специально вводимые знаки раздела (вертикальные линии), ставящиеся между любыми двумя знаками этого выражения (знаками в выражении R являются буквы алфавита Х, символ пустого слова ε, знак дизъюнкции, итерационные и обычные скобки).

Определение.

Кроме этих так называемых разделяющих мест (знаков раздела) вводится еще два места – начальное и конечное. Первое их них располагается слева от самого левого знака выражения 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, переход через букву у – от 6 к 7, непосредственный переход от 7 к 10, непосредственный переход от 10 к 8, переход через букву z – от 8 к 9, непосредственный переход от 9 к 10 и непосредственный переход от 10 к 11.

Пусть R – регулярное выражение, q = x_i1 x_i2 … x_ik произвольное слово во входном алфавите события, представляемого выражением R.

Условимся, что место α в выражении R связано словом q с местом β в том же выражении, если от места α к месту β можно перейти с помощью чередования любого числа непосредственных переходов и переходов через буквы x_i1, x_i2, …, x_ik слова q, взятых по одному разу в том порядке, в каком они входят в слово.

Это условие означает, что место β q–следует за местом α всякий раз, когда α связано с местом β словом q.

Также условимся говорить, что место β подчинено месту α, если от места α к месту β можно перейти с помощью одних лишь непосредственных переходов, т. е. если место α связано с местом β пустым словом ε.

45.Правила подчинения мест в регулярных выражениях.

1. Начальные места всех термов многочлена, помещенного в обычные или итерационные скобки, подчинены месту, находящемуся непосредственно слева от открывающей скобки из пары скобок, в которые заключен данный многочлен (многочлен по этому правилу может вырождаться в одночлен с обязательным заключением его в скобки).

2. Место, расположенное непосредственно справа от закрывающей (итерационной или обыкновенной) скобки подчинено конечным местам всех термов многочлена (в частном случае, одночлена), заключенного в соответствующие скобки, а в случае итерационных скобок – также месту, расположенному непосредственно слева от соответствующей открывающей скобки.

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).

Определение.

Основными местами в таких выражениях считаются по определению все места, непосредственно слева от которых стоит буква основного алфавита, а также начальное место.

Определение.

Все места, непосредственно справа от которых стоит буква основного алфавита, называются предосновными.

46.Правила построения основного алгоритма синтеза конечных автоматов.

1. Заданные регулярные события (число которых предполагается конечным) представляются правильно записанными регулярными выражениями R₁,…,R_p. Все места (как основные, так и не основные) в этих выражениях обозначаются вертикальными черточками (линиями).

2. Каждому основному месту в выражениях R₁,…,R_p приписывается в качестве индекса неотрицательное целое число. При этом всем начальным местам приписывается один и тот же индекс (нуль). Что же касается остальных основных мест, то они нумеруются в произвольном порядке натуральными числами 1, 2, …

Все введенные здесь индексы называются основными. Основные индексы подписываются под вертикальными чертами соответствующих им (основных) мест и подчеркиваются снизу общей для каждого из выражений R₁,…,R_p горизонтальной разделительной чертой.

3. Индекс (основной) каждого основного места α распространяется в качестве неосновного индекса на все места (как основные, так и неосновные), подчиненные месту α, но отличные от него самого.

При этом каждое место β получает некоторое множество неосновных индексов. Все индексы этого множества подписываются в произвольном порядке под вертикальной чертой, соответствующей месту β, ниже разделительной горизонтальной черты. Все индексы (как основные, так и неосновные), относящиеся к любому предосновному месту, заключаются в общую рамку.

4. Строится таблица переходов некоторого автомата Мура. В качестве состояний этого автомата берутся подмножества множества всех основных индексов.

При этом подмножество, состоящее из основных индексов i₁,…, i_k (k≥1), будем обозначать через i₁∨i₂∨…∨i_k, а пустое множество основных индексов – звездочкой (соответствующее ему состояние автомата А называется пустым).

Построение таблицы переходов с состояниями автомата Мура А начинается с вписывания обозначений строк и столбцов таблицы.

Строки таблицы обозначаются (в произвольном порядке) различными буквами входного алфавита заданного множества событий.

Столбцы обозначаются состояниями автомата А, начиная с нулевого. Последующий столбец обозначается в произвольном порядке состоянием из предыдущего столбца после вписывания всех состояний в этот столбец.

На пересечении произвольной (x_i-й) строки и произвольного (qj-го) столбца таблицы вписываются состояния (множества основных индексов), состоящие из основных индексов всех тех и только тех основных мест, которые x_i-следуют за предосновными местами, в числе индексов которых (как основных, так и не основных) находится хотя бы один индекс, принадлежащий состоянию q_j. В случае отсутствия основных мест с требуемыми свойствами на соответствующем месте таблицы вписывается пустое состояние.

Характеристики

Список файлов лекций