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

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

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

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

Широко распространенный на практике класс автоматов Мили получил свое название по имени американского ученого 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; Е – множество всех конечных входных слов ненулевой длины; ε – входное слово нулевой длины (пустое слово); для всех .

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

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

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

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

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

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

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

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

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

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

;

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

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

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

где

1. Теория булевых функций.

49.Связь булевых функций и схем из функциональных элементов и контактных схем.

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

Под функциональным элементом понимается некоторое устройство, внутренняя структура которого нас не интересует и которое обладает следующими свойствами:

1) оно имеет n ≥ 1 упорядоченных отростков сверху – входы и один отросток снизу – выход (см. рис. 5.1);

Рис. 5.1. Функциональный элемент.

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

3) при каждом наборе сигналов на входах устройство на выходе в тот же момент, в который поступили сигналы на входы, выдает один из сигналов 0 или 1;

4) набор сигналов на входах однозначно определяет сигнал на выходе, то есть если в различные моменты времени на входы поступили равные наборы сигналов, то в эти моменты на выходе будет один и тот же сигнал.

Заметим, что с каждым функциональным элементом с n выходами сопоставима булева функция от n переменных f (x₁, x₂,…, x_n), определяемая следующим образом: входу с номером ставится в соответствие переменная x_i и с каждым набором (а₁, а₂,…, а_n) значений этих переменных сопоставляется число f (а₁, а₂,…, а_n), равное 0 или 1 в зависимости от того, какой сигнал вырабатывается на выходе при подаче этого набора сигналов на выходы данного функционального элемента.

В этом случае о функции f (x₁, x₂,…, x_n) будем говорить, что данный функциональный элемент ее реализует, и такой элемент будем изображать так, как показано на рис.5.2.

Рис. 5.2. Реализация функционального элемента булевой функции f (x₁, x₂,…, x_n).

Из функциональных элементов определяется схема из функциональных элементов (точнее схема из функциональных элементов в соответствующем логическом базисе), как-то:

1) , ∧, ∨; 3) , ∨; 5) х ∣ у;

2) , ∧; 4) 1, ∧, ; 6) х ↓ у

и т.д.

Замечания.

1. Учитывая, что существуют определённые аналитические преобразования одного логического базиса в другой, можно изображать схемы в любом логическом базисе и преобразовывать их в другие. Базис, состоящий из логических функций , ∧, ∨ называется нормальным; из логических функций ù, ∨ или ù, ∧ – неполным нормальным; из стрелки Пирса х ↓ у – базисом Вебба; из штриха Шеффера х ∣ у – базисом Шеффера.

Как известно, базис Вебба и базис Шеффера связаны с нормальным базисом следующими аналитическими соотношениями:

х ∣ у = ∨ ; и обратно, = х ∣ х; х ∨ у = (х ∣ х)∣(у ∣ у);

х ↓ у = ∧ ; и обратно, = х ↓ х; х ∧ у =(х ↓ х) ↓ (у ↓ у).

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

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