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

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

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

Рис. 4.2. Совмещенная таблица автомата А₁.

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

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

Пример табличного описания автомата Мура А₂ (рис. 4.3). Для частичных автоматов, у которых функции δ или λ определены не для всех пар (q_m, x_f)∈Q x X, на месте неопределенных состояний и выходных сигналов ставится прочерк или знак Ø.

Рис. 4.3. Таблица переходов автомата Мура.

32.Способы задания автоматов. Граф автомата.

Часто автомат задают с помощью графа автомата.

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

Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Две вершины графа автомата q_m и q_s (исходное состояние и состояние перехода) соединяются дугой, направленной от q_m к q_s, если в автомате имеется переход из q_m в q_s, то есть если q_s = δ (q_m, x_f) при некотором x_f ∈Х. Данной дуге (q_m , q_s) приписывается входной сигнал x_f и выходной сигнал y_g = λ (q_m , x_f). При этом выходной сигнал y_g записывается внутри вершины q_m или рядом с ней.

На рис. 4.4 и 4.5 приведены графы автоматов А₁ и А₂, описанных ранее табличным способом.

Рис. 4.4. Граф автомата А₁

Рис. 4.5. Граф автомата А₂

Любой автомат может быть задан с помощью графа, но не всякий граф в алфавитах Q, X, Y задает автомат. В графе автомата не должно существовать двух дуг с одинаковыми входными сигналами, выходящих из одной и той же вершины (условие однозначности).

33.Способы задания автоматов. Матрица переходов и выходов.

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

Матрица переходов и выходов представляет собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из состояния q_m под действием входного сигнала x_f в состояние q_s, с выдачей выходного сигнала y_i, то на пересечении строки q_m и столбца q_s записывается пара x_f / y_i.

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

Ниже приведены матрицы переходов и выходов для рассмотренных ранее автоматов A₁ и A₂ (рис. 4.6).

Рис. 4.6. Матрицы переходов и выходов автоматов А₁ (а) и А₂ (б).

34.Машины Тьюринга и конечные автоматы.

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

Машины Тьюринга представляют собой абстрактные устройства самого общего типа и являются обобщением автоматов Мили и Мура.

Машины Тьюринга наиболее близки к реальным ЭВМ, так как они представляют собой хорошую математическую модель вычислительной машины. Как показали многочисленные теоретические исследования, классам языков, соответствующим четырем типам грамматики по классификации Хомского, можно поставить во взаимно-однозначное соответствие четыре типа распознающих устройств. Простейшим из них является класс так называемых конечных автоматов, которые допускают (распознают) все языки, порождаемые автоматными (регулярными) грамматиками, и только их.

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

Детерминированным конечным автоматом называют следующую пятерку:

А = (X, Q, δ, q₀, F),

где X = {x₁, ..., x_m} – входной алфавит (конечное множество входных сигналов);

Q = {q₀, q₁, ..., q_n-1} – алфавит состояний автомата (конечное множество символов);

δ – функция переходов;

q₀ ∈ Q – начальное состояние автомата;

F ⊆ Q – множество состояний, называемых заключительными.

На содержательном уровне функционирование конечного автомата можно представить следующим образом. Имеется бесконечная лента с ячейками, в каждой из которых может находиться один символ из Х. На ленте находится цепочка символов α∈ Х*. Ячейки слева и справа от цепочки не заполнены. Имеется некоторое конечное управляющее устройство с читающей головкой, которое может последовательно считывать символы с ленты, передвигаясь слева направо. При этом устройство может находиться в каком-либо одном состоянии из Q. Каждый раз, переходя к новой ячейке, устройство переходит к новому состоянию в соответствии с функцией δ.

На рис. 4.7 изображен конечный автомат в начальном состоянии q₀, считывающий первый символ х_i1 , входной цепочки α_i . Стрелкой показано направление движения читающей головки. Отображение δ можно представить в виде совокупности так называемых команд, которые обозначаются следующим образом:

(q, x) → q′,

где q, q′∈ Q; x = X.

Рис. 4.7. Интерпретация конечного автомата.

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

Число команд автомата конечно, левая часть команды (q, x) называется ситуацией автомата, а правая q′ – есть состояние, в котором автомат будет находиться на следующем шаге своей работы.

Графически команду удобно представлять в виде дуги графа, идущей из вершины q в вершину q′ и помеченную символом х входного алфавита (рис. 4.8).

Рис. 4.8. Графическое представление команды автомата.

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

Полностью отображение δ изображают с помощью диаграммы состояний, то есть ориентированного графа, вершинам которого поставлены в соответствие символы Q, а дугам – команды отображения δ.

Если автомат оказывается в ситуации (q_j, x_i), не являющейся левой частью какой-либо его команды, то он останавливается.

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

Если управляющее устройство считает все символы цепочки α, записанной на ленту, и при этом перейдет в состояние q_f ∈ F (заключительное состояние), то говорят, что цепочка α допускается автоматом А (автомат допускает цепочку α).

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

Множество цепочек, допускаемых данным автоматом, называют языком этого автомата.

Отображение δ можно представить и в виде функции:

δ (q, x) = q′,

где q, q′∈ Q; x ∈ X.

Эта функция интерпретируется так же, как и команда (q, x) → q′. Её можно распространить с одного входного символа на цепочку следующим образом: δ(q, ε) = q, где ε – пустая цепочка;

δ(q, α_x) = δ(δ(q, α), x), где х ∈ Х, α ∈ Х*.

Таким образом, можно сказать, что α допускается автоматом А, если δ(q₀, α) = q_f , где q_f ∈ F, а язык, допускаемый автоматом А, это

L(A) = {α | δ(q0, α)∈ F}.

Пример.

Рассмотрим пример детерминированного конечного автомата

А = (X, Q, δ, q₀, F),

где Х = {a, b}; Q = {S, Y, Z, T}; q₀ = S; F = {T}, а δ задается диаграммой состояний, представленной на рис. 4.9.

Рис. 4.9. Диаграмма состояний детерминированного конечного автомата

Очевидно, что язык, допускаемый этим автоматом,

L(A) = {Mn | n ≥ 1},

где M = {aa, bb}.

Цепочка α1 = aabbaa, допускается данным автоматом, так как после ее просмотра автомат окажется в состоянии Т∈ F.

Цепочка aabba не допускается, так как после ее просмотра автомат окажется в состоянии Y, не являющемся заключительным.

Цепочка abb не допускается потому, что после считывания символа а автомат окажется в ситуации (Y, b), для которой нет команды.

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

Недетерминированный конечный автомат – есть пятерка того же вида. Единственное отличие заключается в том, что значениями функции переходов являются не состояния, а множество состояний (или, в терминах команд, возможны различные команды с одинаковыми левыми частями). Это соответствует тому факту, что в диаграмме состояний из одной вершины может исходить несколько дуг с одинаковой меткой.

35.Машины Тьюринга с двумя выходами.

С точки зрения лингвистики машины Тьюринга можно рассматривать как распознающие устройства, допускающие языки самого широкого из рассмотренных классов: языки типа 0 или рекурсивно-перечислимые множества.

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

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

Лента считается бесконечной. Перед началом работы n ячеек ленты содержат символы входной цепочки α_i = x_i1 , x_i2 ,..., x_in, все остальные ячейки считаются заполненными специальным символом В («пустое место»), который не является входным (рис. 4.10).

Рис. 4.10. Интерпретация машины Тьюринга

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

Формально машина Тьюринга определяется как следующая шестёрка:

Т = (V₁, V₂, Q, δ, q₀, F),

где V₁ = {a₁, ..., a_n} – входной алфавит (конечное множество символов);

V₂ = {А₁, ..., А_k, B} – конечное множество ленточных символов, которое в качестве своего подмножества содержит входной алфавит;

Q = {q₀ , q₁, ..., q_n-1} – конечное множество состояний;

q₀ ∈ Q – начальное состояние;

F ⊆ Q – множество заключительных состояний;

δ – функция, отображающая Q . V₂ в Q . V₂ – {B} . {Л, П}.

(Л и П – специальные символы, указывающие на направление движения головки, лево и право).

Отображение (функцию) δ удобно задавать совокупностью команд вида: (q, A) → (q′, A′, Л) либо (q, A) → (q′, A′, П).

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

Ситуация машины Тьюринга Т – это тройка вида (q, β, i),

где q ∈ Q;

β = A₁, ..., A_n – часть ленты, не содержащая символов В (непустая часть ленты);

i = (0 ≤ i ≤ n+1) – расстояние ленточной (пишущей - читающей) головки от левого конца β; при i = 0 головка находится левее самого левого символа β, при i = n+1 – правее самого правого.

Рассмотрим произвольную ситуацию машины Т:

(q, A₁ ... A_i .... A_n, i), 1 ≤ i ≤ n.

Пусть среди команд отображения δ имеется следующая:

(q, A_i) → (q′, X, Л).

При этом возможно следующее движение (или элементарное действие) машины Тьюринга: головка стирает символ А_i, записывает вместо него символ Х и перемещается на одну ячейку влево.

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

(q, A₁ ... A_i .... A_n, i) ├ (q′, A₁ ... A_i-1 Х A_i+1.... A_n, i -1).

Символ ├ означает – «утверждается».

Аналогично для команды (q, A_i) → (q′, X, П) движение машины Тьюринга записывается как

(q, A₁ ... A_i .... A_n, i) ├ (q′, A₁ ... A_i-1 Х A_i+1.... A_n, i+1).

Кроме рассмотренной ситуации возможны и такие:

(q, A₁ ... A_n, 0);

(q, A₁ ... A_n, n+1).

К ним применимы команды вида:

(q, В) → (q′, X, Л) либо

(q, В) → (q′, X, П).

Первая из этих команд меняет указанные ситуации соответственно следующим образом:

(q, A₁ ... A_n, 0) ├ (q′, X A₁ ... A_n, 0);

(q, A₁ ... A_n, n+1) ├ (q′, A₁ ... A_n X, n).

Вторая из этих команд меняет их так:

(q, A₁ ... A_n, 0) ├ (q′, X A₁ ... A_n, 2);

(q, A₁ ... A_n, n+1) ├ (q′, A₁ ... A_n X, n+2).

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

Если ситуации (q₁, β₁, i₁) и (q₂, β₂, i₂) связаны между собой некоторым числом элементарных действий, то между ними имеет место отношение:

(q₁, β₁, i₁) ├* (q₂, β₂, i₂).

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

Язык, допускаемый машиной Тьюринга Т, это:

L(Т) = {α | α∈ V₁* ∧ (q₀, α, 1) ├* (q_f, β, i)},

где q_f = F, β ∈ V₂*, i ≥ 0.

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

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

Так же как для автоматов введем понятие недетерминированной машины Тьюринга. Её отличие от детерминированной заключается в том, что функция δ отображает множество Q x V₂ в множество подмножеств

Q x (V₂ – {B}) x {Л, П}.

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

Если язык L порождается грамматикой типа 0, то L допускается некоторой машиной Тьюринга. Верно и обратное, если язык L допускается некоторой машиной Тьюринга, то L порождается грамматикой типа 0.

36.Машины Тьюринга и линейно-ограниченные автоматы.

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

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

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

Однако не для всех языков типа 0 эта проблема разрешима.

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

Наибольший интерес представляют различные специальные классы машин Тьюринга, к которым можно отнести автоматы, рассмотренные выше, а также так называемые линейно-ограниченные автоматы, допускающие языки типа 1 (НС-языки).

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

Линейно-ограниченным автоматом называется шестерка:

М = (V₁, V₂, Q, δ, q₀, F),

где V₁ = {a₁, ..., a_m, Z_l, Z_p} – конечный входной алфавит;

V₂ = {А₁, ..., А_k} – конечное множество ленточных символов, причем V₁ ≤ V₂;

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

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