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

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

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

s = (p).

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

Построенное указанным способом отображение будем называть отображением, индуцированным абстрактным автоматом А.

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

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

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

Предположим, что заданы два абстрактных автомата:

А₁ (X₁, Y₁, Q₁, q₁, δ₁(q,x), λ₁(q,x)) и

А₂ (X₂, Y₂, Q₂, q₂, δ₂(q,x), λ₂(q,x)) одного и того же рода.

Если для этих автоматов существуют взаимно однозначные отображения: α – отображающее множество X₁ на множество X₂;

β – отображающее множество Y₁ на множество Y₂; γ – отображающее множество Q₁ на множество Q₂;

и, если удовлетворяются условия:

γ(q₁) = q₂;

γ(δ₁(q₁, x)) = δ₂(γ(q),α(x));

β(λ₁(q,x) = λ₂(γ(q), α(x)) (для любых q∈Q₁ и х∈Х₁),

то абстрактные автоматы А₁ и А₂ называются изоморфными. В этом случае говорят, что отображения α, β и γ осуществляют изоморфное отображение одного автомата на другой.

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

Изоморфные между собой абстрактные автоматы отличаются друг от друга лишь обозначениями входных и выходных сигналов и состояний.

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

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

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

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

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

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

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

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

Произвольные автоматы первого рода, называются автоматами Мили, а частный случай автоматов второго рода, у которых сдвинутая функция выходов λ(q, x) не зависит от второй переменной х – автоматами Мура.

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

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

Первое условие связано с однозначностью функций переходов и выходов и называется – условием однозначности.

Соблюдение этого условия требует, чтобы на графе автомата из любой вершины выходило бы не более одной стрелки, обозначенной конкретным входным сигналом.

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

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

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

Частичным автоматом называется абстрактный автомат, у которого функция переходов или функция выходов (обычная или сдвинутая), или обе эти функции определены не для всех пар значений своих аргументов q и х. В отличие от частичных, ранее рассмотренные автоматы назывались вполне определенными.

41.Автоматные отображения и события.

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

Отображения, индуцируемые абстрактными автоматами, будем называть автоматными отображениями.

Всякое автоматное отображение удовлетворяет следующим четырем условиям автоматности:

1. Автоматное отображение осуществляет однозначное отображение (как правило, частичное) множества слов в некотором конечном алфавите Х (входное алфавитное отображение) в множества слов в некотором конечном алфавите Y (выходное алфавитное отображение).

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

3. Автоматное отображение сохраняет длину слова. Любое слово p входного алфавита на котором отображение определено, имеет ту же длину, что и его образ (p). В частности, пустое слово переводится отображением в пустое слово.

4. Автоматное отображение переводит любой начальный отрезок слова р, на котором оно определено, в соответствующий (имеющий ту же длину) начальный отрезок слова (p).

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

Перечисленные условия (1-4) называются условиями автоматности отображения.

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

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

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

Рассмотрим произвольное (частичное) отображение , для которого выполняются сформулированные выше условия. Построим абстрактный (частичный) автомат Мура U, состояниями которого будут служить всевозможные допустимые для отображения слова входного алфавита

Х=(х₁,…, х_n).

Обозначим множество всех таких слов через А и определим функцию переходов δ(а,x) этого автомата следующим образом: если а_j – любое слово из А, а x_i – произвольная буква входного алфавита, то будем считать, что δ(а_j,x_i) равняется слову а_jx_i (получающемуся в результате приписывания буквы x_i к слову а_j), если слово а_jx_i содержится в А, и что δ(а_j,x_i) не определена в противном случае.

Выбирая в качестве выходного алфавита автомата U выходной алфавит отображения φ, построим сдвинутую функцию выходов λ(а) автомата Мура U следующим образом: для любого непустого слова а_i из А полагаем λ(а_i) равным последней букве слова φ(а_i); на пустом слове функция λ(a) остается неопределенной.

В качестве начального состояния автомата выбираем пустое слово ε и получаем автомат Мура, индуцирующий исходное отображение φ. В самом деле, пусть, q=x_i1,x_i2,…,x_ik – любое допустимое слово отображения φ. Тогда все его начальные отрезки будут также допустимыми словами (в силу условия 2). После подачи на вход построенного автомата слова q, будет осуществляться последовательный его перевод в состояние ε x_i1=x_i1,x_i2,…, x_ik.

При этом автомат выдает некоторую последовательность выходных букв y_j1,y_j2,…,y_jk=p. Из способа определения данного автомата следует, что последняя буква слова р совпадает с последней буквой слова φ(q), предпоследняя буква слова р – с последней буквой слова φ(x_i1,x_i2,…,x_ik-1), которая в силу условия 4, совпадает с предпоследней буквой слова φ(q) и т. д. Продолжая сравнение и используя условия 3, можно установить совпадение всех букв слова р с соответствующими им буквами слова φ(q). Следовательно, построенный автомат Мура U индуцирует исходное (частичное) отображение φ. Поскольку можно интерпретировать автомат Мура U как автомат Мили, то очевидно следующее предложение.

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

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

В случае, когда область определения отображение φ конечна, эти автоматы также можно считать конечными.

Данное предложение позволяет применять термины «автоматное отображение» по всему алфавитному отображению, удовлетворяющему условиям автоматности. Из этого предложения вытекает конструктивный прием, позволяющий по любому автоматному отображению с конечной областью определения (заданному на конечном множестве слов) строить индуцирующий это отображение конечный автомат Мили или Мура.

Ранее рассматривалась возможность интерпретации автомата Мура как автомат Мили с тем же самым числом состояний.

Теорема.

Для всякого конечного автомата Мили существует эквивалентный ему (индуцирующий то же самое отображение) конечный автомат Мура.

Существует единый конструктивный прием (универсальный алгоритм преобразования автоматов Мили в автоматы Мура), позволяющий по произвольному конечному автомату Мили, имеющему m входных сигналов и n состояний, построить эквивалентный ему автомат Мура, имеющий не более m⋅n + 1 состояний.

Условия автоматности накладывают весьма жесткие ограничения на класс отображений, которые могут быть индуцированы абстрактными автоматами. Большинство алфавитных отображений, с которыми приходится иметь дело на практике, в частности большинство алгоритмов, не удовлетворяют этим условиям.

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

Рассмотрим этот прием.

Пусть φ – произвольное (как правило, частичное) отображение множества слов в (конечном) алфавите Х в множество слов в (конечном) алфавите Y. Обозначим через Р область определения этого отображения. Будем применять к отображению φ две операции.

Первая операция – выравнивания длин слов (операция выравнивания).

Её суть: во входной и выходной алфавиты отображения φ (т. е. Х и Y) добавляется по одной новой букве, которые будем называть пустыми и обозначать через α и β.

Каждому слову р из Р приписывается справа mp экземпляров букв α, а к его образу q = φ(p) приписывается слева nq экземпляров букв β так, чтобы длины полученных в результате приписывания новых букв словам р₁ и q₁ совпали.

Далее строится новое отображение φ₁ некоторого множества Р₁, слов в алфавите Х U(α) в множества слов в алфавите Y U (β), которое переводит друг в друга слова р₁ и q₁, полученные в результате выравнивания длин слов р и q соответственно: φ₁(р₁)= q₁ (р – пробегает при этом все множество P). Условимся считать, что отображение φ₁, получается из отображения φ с помощью операции выравнивания. Существует некоторая стандартная операция выравнивания, при которой отображение φ₁, однозначно определяется отображением φ и присоединенными пустыми буквами α и β. Суть ее в том, что число mp пустых букв α, приписываемых справа к произвольному слову р из области определения отображения φ, принимается равным длине слова q = φ(p), а число nq пустых букв β, приписываемых слева к слову q, принимается равным длине слова р.

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

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