Лекции Русакова, страница 13

4.1): Х – алфавит входныхсигналов; Y – алфавит выходных сигналов; Q - алфавит состояний; δ –функция переходов; X – функция выходов122а)б)Рис. 4.1. Таблицы переходов (а) и выходов (б) автомата А1.Автомат, имея один вход и один выход, работает в дискретномвремени, принимающем значения t = 1, 2, 3, ... На вход автомата поступаютвходные сигналы xf (например, сигналы x1 и x2). В каждый момент t автоматнаходится в некотором состоянии q(t), начиная с начального состояния q1.На пересечении столбца qm и строки xf в таблице переходов ставитсясостояние qs = δ (qm, xf), в которое автомат переходит из состояния qm поддействием сигнала xf, а в таблице выходов – соответствующий этомупереходу выходной сигнал yg = λ (qm, xf).Определение.Иногда при задании автоматов Мили используют одну совмещеннуютаблицу переходов и выходов, в которой на пересечении столбца qm истроки xf записываются в виде qs / yg следующее состояние и выдаваемыйвыходной сигнал.На рис. 4.2 представлена совмещенная таблица автомата А1.Рис.

4.2. Совмещенная таблица автомата А1.Определение.123Так как в автомате Мура выходной сигнал зависит только отвнутреннего состояния и не зависит от входного сигнала, то он задаетсяодной отмеченной таблицей переходов, в которой каждому ее столбцуприписан, кроме состояния qm еще и выходной сигнал yg = λ (qm),соответствующий этому состоянию.Пример табличного описания автомата Мура А2 (рис. 4.3).

Длячастичных автоматов, у которых функции δ или λ определены не для всехпар (qm, xf)∈Q x X, на месте неопределенных состояний и выходныхсигналов ставится прочерк или знак Ø.Рис. 4.3. Таблица переходов автомата Мура.4.03. Способы задания автоматов. Граф автомата.Часто автомат задают с помощью графа автомата.Определение.Графавтомата–ориентированныйграф,вершиныкоторогосоответствуют состояниям, а дуги – переходам между ними. Две вершиныграфа автомата qm и qs (исходное состояние и состояние перехода)соединяются дугой, направленной от qm к qs, если в автомате имеется переходиз qm в qs, то есть если qs = δ (qm, xf) при некотором xf ∈Х.

Данной дуге (qm ,124qs) приписывается входной сигнал xf и выходной сигнал yg = λ (qm , xf). Приэтом выходной сигнал yg записывается внутри вершины qm или рядом с ней.На рис. 4.4 и 4.5 приведены графы автоматов А1 и А2, описанных ранеетабличным способом.Рис. 4.4. Граф автомата А1Рис. 4.5. Граф автомата А2Любой автомат может быть задан с помощью графа, но не всякий графв алфавитах Q, X, Y задает автомат.

В графе автомата не должносуществовать двух дуг с одинаковыми входными сигналами, выходящихиз одной и той же вершины (условие однозначности).1254.04. Способызаданияавтоматов.Матрицапереходов и выходов.Определение.Матрица переходов и выходов представляет собой таблицу с двумявходами. Строки и столбцы таблицы отмечены состояниями.

Еслисуществует переход из состояния qm под действием входного сигнала xf всостояние qs, с выдачей выходного сигнала yi, то на пересечении строки qm истолбца qs записывается пара xf / yi.Для автомата Мура используется матрица, столбцы которой отмеченывыходными сигналами yi, а на пересечении ее строк и столбцов указываютсятолько входные сигналы xf.Ниже приведены матрицы переходов и выходов для рассмотренныхранее автоматов A1 и A2 (рис. 4.6).Рис. 4.6.

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

Простейшим из нихявляется класс так называемых конечных автоматов, которые допускают(распознают)всеязыки,порождаемыеавтоматными(регулярными)грамматиками, и только их.Определение.Детерминированным конечным автоматом называют следующуюпятерку:А = (X, Q, δ, q0, F),где X = {x1, ..., xm} – входной алфавит (конечное множество входныхсигналов);Q = {q0, q1, ..., qn-1} – алфавит состояний автомата (конечное множествосимволов);δ – функция переходов;q0 ∈ Q – начальное состояние автомата;F ⊆ Q – множество состояний, называемых заключительными.На содержательном уровне функционирование конечного автоматаможно представить следующим образом. Имеется бесконечная лента сячейками, в каждой из которых может находиться один символ из Х.

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

Каждый раз, переходя к новой ячейке,устройство переходит к новому состоянию в соответствии с функцией δ.На рис. 4.7 изображен конечный автомат в начальном состоянии q0,считывающий первый символ хi1 , входной цепочки αi . Стрелкой показанонаправлениедвижениячитающейголовки.Отображениеδможнопредставить в виде совокупности так называемых команд, которыеобозначаются следующим образом:(q, x) → q′,где q, q′∈ Q; x = X.Рис. 4.7. Интерпретация конечного автомата.Определение.Число команд автомата конечно, левая часть команды (q, x) называетсяситуацией автомата, а правая q′ – есть состояние, в котором автомат будетнаходиться на следующем шаге своей работы.128Графически команду удобно представлять в виде дуги графа, идущейиз вершины q в вершину q′ и помеченную символом х входного алфавита(рис. 4.8).Рис. 4.8. Графическое представление команды автомата.Определение.Полностью отображение δ изображают с помощью диаграммысостояний, то есть ориентированного графа, вершинам которого поставленыв соответствие символы Q, а дугам – команды отображения δ.Если автомат оказывается в ситуации (qj, xi), не являющейся левойчастью какой-либо его команды, то он останавливается.Определение.Если управляющее устройство считает все символы цепочки α,записанной на ленту, и при этом перейдет в состояние qf ∈ F(заключительное состояние), то говорят, что цепочка α допускаетсяавтоматом А (автомат допускает цепочку α).Определение.Множество цепочек, допускаемых данным автоматом, называютязыком этого автомата.Отображение δ можно представить и в виде функции:δ (q, x) = q′,где q, q′∈ Q; x ∈ X.129Эта функция интерпретируется так же, как и команда (q, x) → q′.Её можно распространить с одного входного символа на цепочку следующимобразом: δ(q, ε) = q, где ε – пустая цепочка;δ(q, αx) = δ(δ(q, α), x), где х ∈ Х, α ∈ Х*.Таким образом, можно сказать, что α допускается автоматом А, еслиδ(q0, α) = qf , где qf ∈ F, а язык, допускаемый автоматом А, этоL(A) = {α | δ(q0, α)∈ F}.Пример.Рассмотрим пример детерминированного конечного автоматаА = (X, Q, δ, q0, F),где Х = {a, b}; Q = {S, Y, Z, T}; q0 = S; F = {T}, а δ задается диаграммойсостояний, представленной на рис.

4.9.Рис. 4.9. Диаграмма состояний детерминированного конечного автоматаОчевидно, что язык, допускаемый этим автоматом,L(A) = {Mn | n ≥ 1},где M = {aa, bb}.Цепочка α1 = aabbaa, допускается данным автоматом, так как после еепросмотра автомат окажется в состоянии Т∈ F.Цепочка aabba не допускается, так как после ее просмотра автоматокажется в состоянии Y, не являющемся заключительным.130Цепочка abb не допускается потому, что после считывания символа аавтомат окажется в ситуации (Y, b), для которой нет команды.Определение.Недетерминированный конечный автомат – есть пятерка того жевида. Единственное отличие заключается в том, что значениями функциипереходов являются не состояния, а множество состояний (или, в терминахкоманд, возможны различные команды с одинаковыми левыми частями). Этосоответствует тому факту, что в диаграмме состояний из одной вершиныможет исходить несколько дуг с одинаковой меткой.4.06. Машины Тьюринга с двумя выходами.С точки зрения лингвистики машины Тьюринга можно рассматриватькак распознающие устройства, допускающие языки самого широкого израссмотренных классов: языки типа 0 или рекурсивно-перечислимыемножества.Определение.Машина Тьюринга состоит из конечного управляющего устройства,входной ленты и головки, которая в отличие от головки конечного автоматаможет не только считывать символы с ленты, но и записывать на нее новыесимволы.Лента считается бесконечной.