lekcii_dm

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

Доказано также, что если L(G2) – бесконтекстный язык, порождаемый грамматикой G2 = (VN, VT, P, S), являющейся формой произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М, такой, что L1(M) = L(G2).

При этом

М = (V, Q, Vм, δ, q0, z0, 0),

где V = VT; Q = {q0}; Vм = VN ; z0 = S, а для каждого правила G2 вида А → а α, а VТ,

α VN* строится команда отображения δ: (q0, а, А) → (q0, α).

Аналогично, для любого недетерминированного магазинного автомата М, допускающего язык L1(M), можно построить бесконтекстную грамматику G такую, что L(G) = L1(M).

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

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

141

4.10. Модель дискретного преобразователя Глушкова В. М.

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

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

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

Абстрактный автомат А задается совокупностью шести объектов:

А = (Х, Y, Q, q0, δ, λ),

где Х – конечное множество входных сигналов, называемое входным алфавитом автомата;

Y – конечное множество выходных сигналов, называемое выходным алфавитом автомата;

Q – произвольное множество, называемое множеством состояний автомата;

q0 – элемент из множества Q, называемый начальным состоянием автомата;

δ(q, x) и λ(q, x) – две функции, задающие однозначные отображения множества пар (q, x), где q Q и x X, в множества Q и Х. Функция δ(q, x) называется функцией переходов автомата, а функция λ(q, x) – функцией выходов, либо сдвинутой функцией выходов.

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

Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.

142

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

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

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

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

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

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

каждое слово p = xi1, xi2, …, xik входного алфавита X = (x1, x2, …, xn) или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предварительно в начальное состояние.

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

144

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

s = (p).

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

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

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

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

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

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

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

А1 (X1, Y1, Q1, q1, δ1(q,x), λ1(q,x)) и

А2 (X2, Y2, Q2, q2, δ2(q,x), λ2(q,x)) одного и того же рода.

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

β – отображающее множество Y1 на множество Y2; γ – отображающее множество Q1 на множество Q2;

и, если удовлетворяются условия: γ(q1) = q2;

γ(δ1(q1, x)) = δ2(γ(q),α(x));

β(λ1(q,x) = λ2(γ(q), α(x)) (для любых q Q1 и х Х1),

145

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

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

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

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

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

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

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

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

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

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

146

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

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

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

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

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

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

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

Второе условие, называется условием определенности, требующим,

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

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

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

147

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

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

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

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

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

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

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

3.Автоматное отображение сохраняет длину слова. Любое слово p

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

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

148

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

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

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

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

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

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

150