Ещё одни лекции (1021740), страница 13

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

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

Места 2, 4 кроме самих себя, подчинены месту 1 (по правилу 1).

Место 6 и 8 – месту 5 (по правилу 1) и месту 10 (по правилу 3).

Место 10 подчинено (кроме самого себя) местам 5,7 и 9 (по правилу 2).

Место 11 подчинено (кроме самого себя) местам 3 и 10 (по правилу 2) и местам 5, 7 и 9 (по правилу 5).

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

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

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

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

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

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. В случае отсутствия основных мест с требуемыми свойствами на соответствующем месте таблицы вписывается пустое состояние.

5. Каждое из состояний i₁∨i₂∨…∨i_k (k≥1), обозначающее столбцы таблицы переходов, отмечается множеством (R_j1, …, R_jm) всех символов тех и только тех регулярных выражений R₁,…,R_p, конечные места которых содержат в числе своих индексов (как основных, так не основных) хотя бы один из индексов i₁,…,i_k.

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

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

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

Событие, заданное регулярным выражением R, представляется множеством всех тех и только тех состояний, которые отмечены множествами, содержащими в качестве своих элементов выражение R_i. Это же событие (за вычетом лишь пустого слова, если оно содержится в событии) представляется в автоматах А и В множеством всех тех и только тех выходных сигналов (множеств), состоящих из выражений R₁,…,R_p, которые содержат в своем составе выражение R_i(i = 1,..., p). Множество состояний, отмеченных пустым множеством ( ), или выходной сигнал ( ) представляет событие, состоящее из всех слов входного алфавита, не вошедших в заданные события.

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

Пример.

Рассмотрим пример синтеза конечного автомата в соответствии с описанным алгоритмом.

Пусть требуется построить конечный автомат, в котором для входного алфавита Х, состоящего из двух букв х и у, были бы представлены два события: событие R₁, состоящее из всех слов в алфавите Х, в которых все буквы х предшествуют всем буквам у, и событие R₂, состоящее из всех слов в алфавите Х, которые кончаются буквой х.

Применяя правило 1, записываем заданные события в виде следующих регулярных выражений:

После разметки мест эти выражения приобретут вид:

Применяем правило 2, в результате получим выражения:

В результате применения правила 3 получаем:

Применение правила 4 приводит к построению таблицы переходов 4.1.

Применение правила 5 дает отмеченную таблицу переходов 4.2.

Обозначая выходные сигналы ( ), (R₁), (R₂), (R₁, R₂) соответственно через z, u, v и w и, нумеруя состояния, переходим к отмеченной таблице переходов 4.3.

При интерпретации построенного автомата как автомата Мили в соответствии с правилом 6 мы получим таблицу его выходов 4.4.

Построенные автоматы представляют событие R₁ состояниями 1, 2, 3, а событие R₂ – состояниями 2, 4. Событие R₁ за вычетом содержащегося в нем пустого слова представляется также выходными сигналами u и w, а событие R₂ – выходными сигналами v, w. Состоянием 2 или, что то же самое, выходным сигналом w представлено пересечение событий R₁ и R₂ .

Таблица 4.1

Таблица 4.2

Таблица 4.3

Таблица 4.4

Построенные автоматы представляют событие R1 состояниями 1, 2, 3, а событие R₂ – состояниями 2, 4. Событие R₁ за вычетом содержащегося в нем пустого слова представляется также выходными сигналами u и w, а событие R₂ – выходными сигналами v, w. Состоянием 2 или, что то же самое, выходным сигналом w представлено пересечение событий R₁ и R₂ .

44.Автомат Мили.

Широко распространенный на практике класс автоматов Мили получил свое название по имени американского ученого G. Н. Меаlу, впервые исследовавшего эту модель.

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

Автоматом Мили называется автомат, выходные слова которого зависят как от внутренних состояний автомата, так и от значений входных слов.

Оператор автомата Мили (автомата с памятью) полностью описывается функцией переходов q(t +1) и функцией выходов y(t).

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

Закон функционирования автомата Мили задается уравнениями:

q (t+1) = δ(q(t), x(t)),

y (t) = λ(q(t), x(t)), где t = 0,1,2,…

Конечный автомат А описывается выражением:

А = (Q, X, Y, δ, λ, q₀),

в котором заданы входной и выходной алфавиты, алфавит состояния, а также функции переходов и выходов.

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

Многие же задачи можно решать, описывая автомат без начального состояния q₀:

А = (Q, X, Y, δ, λ).

Функцию переходов δ и функцию выходов λ определим на их множестве пар <состояние – входное слово>.

Пусть ξ = x_i1 x_i2 …x_ik – входное слово длины k; Е – множество всех конечных входных слов ненулевой длины; ε – входное слово нулевой длины (пустое слово); для всех .

Тогда функцию заключительного состояния определим в множестве следующем образом:

45.Автомат Мура.

Автомат Мура получил название по имени впервые исследовавшего эту модель американского ученого E. F. Moore.

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

Автоматом Мура называется автомат, выходные слова которого зависят только от внутренних состояний автомата и не зависят непосредственно от входных слов.

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

Закон функционирования автомата Мура задается уравнениями:

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

Функция заключительного состояния в множестве определяется также, как и для автомата Мили.

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

;

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

Функция – реакция автомата в состоянии на входное слово – не определена, если не определена.

Если определена, то:

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

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