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

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

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

где .

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

Закон функционирования абстрактного автомата второго рода – уравнением:

,

где .

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

37.Понятие об абстрактном автомате и индуцируемом им отображении.

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

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

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

Отображение реализации некоторого отображения реализуется следующим образом:

каждое слово p = x_i1, x_i2, …, x_ik входного алфавита X = (x₁, x₂, …, x_n) или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предварительно в начальное состояние.

Возникающая таким образом конечная последовательность входных сигналов x(1) = x_i1, x(2) = x_i2, …, x(k) = x_ik на основании закона функционирования автомата вызывает появление однозначно определенной конечной последовательности s = y(1), y(2), …, y(k) выходных сигналов. Эту последовательность будем называть выходным словом, соответствующим входному слову р.

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

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 и х. В отличие от частичных, ранее рассмотренные автоматы назывались вполне определенными.

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

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

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

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

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 как автомат Мили, то очевидно следующее предложение.

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

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

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

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

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

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