.RU

Основные понятия теории автоматов


Теория автоматов.


ВВОДНЫЕ ПОЛОЖЕНИЯ.


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


В этой теории достаточно четко выявляются ее направления, обусловленные:

  1. выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)

  2. принятым уровнем абстракции (абстрактные и структурные автоматы)

  3. спецификой применяемых математических (алгебраическая теория автоматов)

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


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


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

^ ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ



  1. Абстрактный конечный автомат U- модель , представляющая устройство, которое преобразует информацию по правилам R в виде «черного ящика», имеющего входной А и выходной В алфавиты, а также некоторое множество внутренних состояний Q.




ai  A, bj  B, qk  Q


Когда на вход подается сигнал ai, то в зависимости от него и текущего состояния qk  Q автомат переходит в следующее состояние ql  Q и выдает сигнал на выход bj  B. Это – один такт действия автомата qk ai ql bj. Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

  1. ^ Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.

  2. Ситохастический (вероятностный) автомат - абстрактный автомат, правила преобразования информации которого R являются вероятностными.

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

  4. Структурный автомат - конечный автомат, внутреннее устройство которого известно.

  5. ^ Формальная грамматика = - система правил построения P в заданном алфавите TH(T – терминальный алфавит, Н – нетерминальный алфавит, ТН=) конечных знаковых последовательностей, множество которых образует некоторый формальный язык () (JH, Н - аксиома).

  6. ^ Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой ).

  7. Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TH) обозначать греческими буквами; так, например,  (TH)*).

  8. Предложение – слово в терминальном алфавите.

  9. Продукция (синтаксическое правило) – способ преобразования цепочки вида  (, ,  (TH)*) в цепочку вида  ((TH)*).

  10. Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.


^ АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.


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


Тип языка () по Хомскому

Тип формальной грамматики Хомского


Автоматная модель языка


0

Произвольная (алгоритмическая) грамматика типа 0 


Машина Тьюринга


1

Грамматика типа 1 (контекстная грамматика, Н.С.грамматика, грамматика непосредственно составляющих) В


Автомат с линейно-ограниченный памятью


2

Грамматика типа 2(контексно-свободная грамматика, К.С.грамматика, бесконтекстная грамматика) В


Магазинный автомат


3

Грамматика типа 3(автоматная, регулярная, конечная)

ВаС, Ва


Конечный автомат




Классы языков по Хомскому являются иерархией, т.е. язык типа 3 является подклассом языка типа 2, т.е. (3) (2) (1)  (0). Следуя приведенной таблице, можно говорить, что

  1. регулярный язык (т.е. язык, порождаемый грамматикой типа 3) распознается конечным автоматом и в этом плане является самым простым в математическом плане

  2. бесконтекстный язык (т.е. язык (2)) распознается магазинным автоматом – бесконечным автоматом, внутренняя структура которого представляет собой стековую память

  3. контекстный язык (1) распознается автоматом с линейно-ограниченной памятью, т.е. автоматом, которому для распознавания последовательности длины nN необходима память объемом не более k*n, где k – число, независящее от входного слова

  4. произвольный формальный язык, т.е. (0), распознается машиной Тьюринга – математического понятия для формального уточнения интуитивного понятия «алгоритм»

Замечание: В синтаксическом правиле В являются контекстами (левый и правый), которые могут быть пустыми цепочками; ВН, а,, ,   (ТН).


^ ФОРМАЛЬНЫЕ ГРАММАТИКИ.


Формальные грамматики = как процедуры могут быть порождающими и распознающими. Порождающая грамматика по существу является частным случаем формальной системы FS/=-=. В этом случае A=TH, F(TH)*, JH, P=iji, jN, i, j(TH)*, т.е. правила вывода P позволяют получать слова в терминальном алфавите Т из единственной аксиомы J путем замещения нетерминальных символов цепочек в алфавите (TH).

^ Распознающая грамматика – алгоритм, распознающий по любой цепочке, является ли оно словом языка  T*.

Автомат для распознавания и порождения слов можно рассматривать как устройство обработки входных цепочек символов с целью:

  1. определения их принадлежности формальному языку ()

  2. порождений выходных цепочек символов


Выводом в грамматике  называется последовательность цепочек, в которой каждая из цепочек, кроме первой, получается из предыдущей применением какого-либо правила вывода (последняя цепочка в выводе – предложение, т.е. слово В в алфавите Т).

Пример 1: Т=a, b, c, H=B, C, J=B, P=BaBc, BCc, Cb

Возможным выводом в этой грамматике может быть последовательность слов:

В, аВС, аСсС, аbсС, аbсbТ*

Эта грамматика порождает язык b, bc, abcb.

Пример 2: множество нечетных чисел в унарном представлении – это множество терминальных слов вида а, ааа, ааааа….., т.е. язык =хТ*: ха2n-1, nN. Этот язык порождается автоматной грамматикой 3=.

Пример 3: Язык =хТ*: х=anbnnN порождается К.С. грамматикой, т.е. 2=.

Пример 4: Язык булевых формул с переменными x, y, z порождается К.С. грамматикой 2=.


^ ДЕРЕВЬЯ ВЫВОДА ПРЕДЛОЖЕНИЙ.


На практике вывод слов языка () в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу ri: 1A212 (здесь 1, 2 – контекст, 1, 2 (TH)*), АН, (TH)*) поставлено в соответствие элементарное поддерево t(ri) с вершиной А и кроной 12.


Пример 1: Пусть 1=.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:



A

Здесь J – корень дерева, J A , A a - поддеревья.


B

aabc – крона дерева синтаксического вывода(a, b, b, c – листья дерева ).


Пример 2: Арифметическое выражение a*b+c в К.С. грамматике с продукциями P=JB, JJ+B, BC, BBC, CD, Da, Db, Dc  имеет следующий вывод: J, J+B, B+B, BC+B, CC+B, DC+B, aC+B, ab+B, ab+C, ab+D, ab+c (этот вывод содержит 52 символа). Дерево этого вывода имеет вид:


J



J + B


B C


B * C D


C D c


D b


a


В этом дереве синтаксического вывода 16 вершин, из них 5 помечены терминальными символами (крона а, *, b, +, с), а 11 – нетерминальными (равно числу применения правил в выводе терминальной цепочки a*b+c).


Примечание:

  1. Однозначное соответствие между выводом и его синтаксическим деревом не означает однозначность обратного – одному дереву может соответствовать несколько выводов. Так, в рассмотренном примере арифметическое выражение в грамматике может иметь и другой вывод: J, J+B, B+B, Bc+B, BD+B, Bb+B, Cb+B, Db+B, ab+B, ab+C, ab+D, ab+c, а его дерево тоже самое, что в рассмотренном примере.

К.С. грамматика 2 может быть нефункциональной, если в ней существует хотя бы одно предложение языка , имеющее более одного дерева синтаксического вывода.
Так К.С. грамматика порождает язык , цепочки которого с n>1 имеют несколько выводов и соответственно несколько деревьев синтаксического вывода. Действительно, предложение a7 представимо двумя деревьями вывода




3) Поскольку дерево синтаксического вывода является средством вывода терминального слова, что наличие нескольких деревьев для вывода влечет за собой семантическую неоднозначность (т. е. различные интерпретации одного и того же слова).
^ Так, нефункциональная К. С. грамматика
позволяет для выравнивания a∙b+c задать два дерева синтаксического вывода





Интерпретацией этих двух деревьев для цепочки a∙b+c являются различные расстановки скобок – в первом случае (a∙b)+c, а во втором a∙(b+c), что означает включение в терминальный алфавит Т грамматики σ скобок (левой и правой).


Теорема: не существует алгоритма распознавания для произвольной К. С. грамматики, ее функциональности или нефункциональности.


4) Процесс распознавания правильности цепочки (слова, предложения), т. е. определения ее принадлежности к рассматриваемому языку ,

называют синтаксическим анализом (в ЭВМ этот анализ осущуствляет распознаватель – один из основных блоков современных трансляторов t(αех) = αобъект, где t – транслирующая программа). При анализе цепочек используется либо стратегия “развертый” (т. е. сверху вниз – от корня дерева вывода к его кроне), либо стратегия “свертый” (т. е. снизу вверх – от кроны к корню дерева вывода).


Ех.: провести синтаксический анализ предложения

методом “развертый” и “свертый”, если продукции σ2 имеет вид: Р={J→Ca, C→bA, C→aB, A→a, B→b, B→bC}.


Решение:


а)





б)

1) 2) 3)


4) 5) 6)




^ Пояснения к построению дерева методом “свертый”:

  • входная цепочка (предложение) является кроной (полагаем);

  • получаемые в процессе свертки подстроки сравниваются с правыми частями продукций грамматики σ2, а при их совпадении приводятся к нетерминальному символу, стоящему в левой части таких продукций.

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


Регулярная грамматика и конечный автомат.

Любая регулярная грамматика может быть представлена взвешенным графом . В графе ; где K- множество концевых вершин (узлов), V – множество узлов, - множество дуг орграфа .

При этом

  1. если А-грамматика имеет продукции вида B→аC, то узел орграфа, помеченный нетерминальным символом с помощью дуги, помеченной терминальным символом , соединяется с вершиной .

  2. Если грамматика σ3 имеет продукции вида B→а, то узел соединен дугой, помеченной символом , с концевой вершиной .

  3. При наличии в А-грамматике правил вида В→Λ (где Λ – пустая цепочка, ,), каждый нетерминальный символ, для которого имеет место такое правило, считается концевой вершиной.


Ех.: пусть .

Граф этой грамматики имеет вид





позволяющий записать порождаемый σ3 язык α(σ3), а предложениями α(σ3) будут цепочки aa и bb. Действительно, деревья вывода следующие:





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

Примечание. Говорят, что конечный взвешенный орграф , имеющий один начальный узел и один или несколько конечных узлов, есть конечный автомат , распознающий язык (здесь - концевые вершины, q1 – начальное состояние).


Ех. Пусть имеем диаграмму автоматной граммтики вида:





Очевидно, что имеем продукции Р={J→aJ, J→aB, B→bB, B→b}, порождающие язык .


Замечание. Графовое представление А-грамматики можно рассматривать не только как удобный аппарат порождения предложений соответствующего автоматного языка α(σ3), но и как анализатор, распознающий слова, принадлежащие этому языку, и вырабатывающий их синтаксическую структуру.


Теорема. Для каждой автоматной грамматики σ3 можно построить эквивалентный ей конечный распознающий автомат (анализатор) .


Машины Тьюринга как распознаватели.

Машина Тьюринга – гипотетическая вычислительная машина, предложенная Аланом Тьюрингом в 1936 г. для уточнения эффективной процедуры (алгоритма) вычислений.

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





предполагается, что блок управления, являющийся конечным автоматом, имеет конечное число состояний Q={q0, q1,…, qn}, где q0 – начальное (исходное) состояние блока.
Предполагается, что “программа” машины Тьюринга составляется из конечного множества команд вида: qi aj→ ql ak dp , , где (и ).
Смысл команды следующий: блок управления, находясь в состоянии qi после считывания головкой символа aj из ячейки ленты должен перейти в состояние ql головки, записать в обозреваемую ячейку символ ak и передвинуть на один шаг dp(dp - влево, dп - вправо, dн - остаться неподвижной).

Говорят, что функция f: N0K N0, где N0=N0 является вычислимой по Тьюрингу, если для каждого слова  N0K справедливо утверждение, что при помещении некоторого представления  N0K на ленту(и в предложение начального состояния) машина останавливается в случае считывания с ленты представления функции f().

Замечание:

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

В недетерминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы.

2) на языке соответствий множество команд для рабочей недетерминированной машины Тьюринга есть отображение q=< M1, M2, S> , где

M1= A* Q, M2=A*Q*D, S: A*Q A*Q*D, DomS A*Q

( Если DomS= A*Q, то говорят о всюду определенной машине Тьюринга,

а если DomS A*Q, то о частично определенной машине.)

JmS A*Q*D
При этом : если S=Sf , то машина Тьюринга является детерминированной, не всюду определенной машиной, а в случае S|=Гf (?)–детерминированной всюду определенной машиной.
Формально машина Тьюринга UT есть кортеж , где AQ=Ф и

A={a0 , a1 , a2 … am } –внешний алфавит

Q={q0 , q1 , q2 … qn } –внутренний алфавит

Р- законы взаимодействия алфавитов А и Q.

В случай детерминированной машины Тьюринга ее законы взаимодействия символов Р представляют программу П( рассматривается как упорядоченной множество команд) и в этом случае записывают UT= ,

где П={ xP: qiaJ qeaKdp}

Как формальная система F.S. машина Тьюринга порождает множество своих конфигураций К (машинных слов вида d1qe 2, где 1 2A* , qeQ). Исходный объект – начальная конфигурация q0 1 2 , правила Р- система команд. Особенность F.S., задающих алгоритм (в нашем случае машину Тьюринга), заключается в том, что в них любому порождаемому объекту ( в нашем случае конфигурация машины Тьюринга) применимо одно правило. Именно это свойство обеспечивает детерминированность (однозначность) работы алгоритма.


Пример: Последовательность конфигураций машины Тьюринга < a0 +, {q1, q2, q3, qz}>, реализующей в унарной системе счисления алгоритм сложения двух натуральных чисел следующий:


A\ Q

q1

q2

q3

|

a0dnq3

|d^ q2

|dnq3

a0

a0dnq1

a0dHq1

|dHq2

+

a0dnq2

+d^ q2

+dnq3


Конфигурация

№1 q1=|||+||||

q1


a0

a0

|

|

|

+

|

|

|

|

a0

a0







q1 a0dnq3
2 q3=|||+||||

k1| k2


a0

a0

a0

|

|

+

|

|

|

|

a0

a0



q3


№9 (3+4+2)

|
q3 |dnq3
|+||||q3

k3| k9


a0

a0

a0

|

|

+

|

|

|

|

a0

a0



q3


№10 ||+||||q2


a0q3 |dHq2


k9| k10



a0

a0

a0

|

|

+

|

|

|

|

a0

a0



q2


№18 (2*(3+4+2))

||+|||||


a0q2 |d^q2


k17| k18



a0

a0

a0

|

|

+

|

|

|

|

|

a0



q2


№19 a0q1 ||+|||||

a0q2 a0dnq2


k18| k19



a0

a0

a0

|

|

+

|

|

|

|

|






q1


№20

?? a0dnq3


k19| k20



a0

a0

a0

a0

|

+

|

|

|

|

|

a0



q3

№55


?? a0dnq1


k54| k55



a0

a0

a0

a0

+

|

|

|

|

|

|

|

a0



№56


?? a0dnq1(??)


k55| k56



a0

a0

a0

a0

??

|

|

|

|

|

|

|

a0
q2

Пояснения: Из начальной конфигурации q1|||+||| сотрем самую левую палочку, машина Тьюринга (далее UT) перейдет в состояние q3 и передвинется по ленте вправо (см. в программе П верхнюю левую ячейку) т.к. реализована команда

|q1a0dnq3. Затем UT перейдет направо через все палочки и знак суммы +(см. в программе П верхнюю и нижнюю правые ячейки) до пустой ячейки a0, поставит в ней палочку и перейдет в состояние q2. Далее UT, выполняя команды среднего столбца программы П перейдет влево, пока не окажется у пустой ячейки a0. Переместившись на один шаг вправо, UT перейдет в начальное состояние q1, завершив тем самым первый цикл работы (число циклов равно трем). После третьего цикла UT, попав в конфигурацию q1+||||||, сотрет знак суммы + и перейдет в заключительное состояние qz (т.е. машина остановится0, а на ленте останется результат вычисления- семь палочек.


Примечания:

  1. Рассмотренная машина Тьюринга существует для любого рекурсивно-перечислимого множество слов (цепочек) М()- слов , порождаемых машиной при ее переходе из начального состояния q1 в заключительное qz, т.е ( q1,)=qz. Однако, это не значит, что для любого такого множества М() может быть решена проблема распознавания.

  2. Для того, чтобы машина Тьюринга существовала для любого рекурсивного автоматно-разрешимого множества слов(нужно не только построить порождающую слова машину (т.е. когда Т()=), но и уметь определить такие , обрабатывая которые она не может перейти в заключительное состояние qz= ( q1,) (т.е. вычисляемое машиной Тьюринга значение функции на этих аргументах не определено). В общем случае эта проблема разрешима. Однако эта проблема оказывается разрешимой для некоторых классов машин Тьюринга – линейно-ограниченных, магазинных и конечных автоматов.


Напоминания:

  1. Множество, характеристическая функция которого есть рекурсивная (вычислимая) функция, называется разрешимым (рекурсивным) .

  2. Множество значений рекурсивной функции называется перечислимым (рекурсивно-перечислимым)


^ Линейно-ограниченные автоматы.

(Машина Тьюринга с ограниченной рабочей лентой)

Машина Тьюринга UТ, которой для распознания слова А* длины n (пишут ||=n) необходима внешняя память с числом ячеек не более k,n, где k- число, не зависящее от анализируемой ячейки, называется автоматом с линейно-ограниченной памятью . Эти автоматы распознают контекстные языки.

Работа Л-О. автомата состоит из следующих этапов:

  1. Просматривается слева направо записанное на ленте предложение и первая и последняя его буквы заменяются на нетерминированные символы.

  2. ищет в слове подцепочки, являющиеся правыми частями определяющих его (автомата) работу правила НС-грамматики. Если такая подцепочка найдена, автомат заменяет правую часть соответствующего правила (т.е. найденную подцепочку) на левую часть. При этом в случае, если длина левой части правила меньше длины правой, то в оставшиеся свободные ячейки записывается так называемый «нейтральный» символ, не влияющий на работу Л.О. автомата. Если анализируемая цепочка входит в язык (), то должен найтись такой вариант работы Л.О.-автомата, при котором эта цепочка может быть преобразована в цепочку, состоящую из начального символа грамматики и последовательности нейтральных символов. В этом случае начинается третий этап работы.

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


Пример: Построить распознающий ЛО-автомат для НС-языка (1)={anbnan}, если 1- грамматика имеет следующие продукции:

JMCM, CMCBM, Cb, MBKB, KBKM, KMBM, bBbb, Ma

Решение:

Рассмотрим работу ЛО-автомата при анализе терминальной цепочки aaabbbaaa, выводимой в данной грамматике следующим образом:

J MCM, MMCBMM, MMMCBMBMM, MMMCBKBMM, MMMCBKMMM, MMMCBBMMM, MMMbBBMMM, MMMbbBMMM, MMMbbbMMM, aMMbbbMMM, aaMbbbMMM, aaabbbMMM, aaabbbaMM, aaabbbaaM, aaabbbaaa.

С учетом того, что вывод предложения a3b3a3(1) возможен в эквивалентной грамматике с продукциями:

JaCa, CaCBa, Cb, aBBa bBbb.

Представим конфигурации ЛО-автомата. в которые он приходит при распознавании следующей цепочки:

a0q1 aaabbbaaa a0| a0D q1aabbbaaa a0 |-- a0Daabbbaaaq1…

|-- q2DaabbbaaaA |-- …|-- Daabq2bbaaA |--…|--q2DaabbBaaA|--…

|--Daaq2bbBaaA |--…|-- q2DaabBBaaA |--…|--Daaq2bBBaaA |--…

|-- q2DaaCBBaaA |--…|-- DaaCBq2BaaA |--…|--q2DaaCBaBaA |--…

|-- Daq2aCBaBaA |-- …|--q2DaCнннBaA|--…|--Dq2aCнннBaA …

|--q2DcннннннА|-- q?*|--q2aCннннннa|--…|--q2Jннннннн |--…|-- Jннннннннqz


Примечания: Если анализируемая цепочка не входит в язык (1)={anbnan}, то ЛО-автомат при любом варианте анализа перейдет в тупиковую ситуацию. Например, один из вариантов анализа цепочки abaa следующий:

q1abaa |--…|--q2DbaA |--…|--…Dq2baA |--…|--q2DcaA |--…|--q2aCaa|--q2Jннa |--…

|--Jннq2a –тупик.

Итак, алгоритм распознавания инициальным ЛО – автоматом , здесь q0 – начальное состояние, F – множество заключительных состояний,

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

  • Образуется всевозможные конфигурации автомата длиной ℓ+1(ℓ- длина исходной цепочки , к которой добавляется единица – символ состояния qi). Таких конфигураций конечное множество;

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

  • Выделяется подмножество последовательностей, начинающихся с конфигураций до α и заканчивающихся конфигурациями вида . Если среди этих последовательностей найдется такая, которая определяет возможный вариант работы ЛО – автомата, цепочка допускается (т.е. распознана как элемент языка) автоматом, в противном случае – не допускается.

Теорема. Классы языков, допускаемых ЛО – автоматами, и НС – языков совпадают.


Магазинные автоматы( МП – автоматы).

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

а) Магазинная память.

Магазинная (стековая) память является аппаратной реализацией машинного списка – стека. Запись и считывание в ней осуществляется через одну и ту же ячейку – вершину стека. В этом случае говорят, что стек (классический пример его – магазин пистолета) реализует дисциплину LIFO(последним пришел первым ушел) в безадресной памяти. Схематично магазин можно рассматривать как потенциально бесконечную в одну сторону ленту, состоящей из ячеек, пронумерованных последовательно числами натурального ряда N. Лента расположена вертикально так, что первая ячейка оказывается самой верхней для записи считывания символа слова. В каждый момент времени в магазине хранится некоторая цепочка, при чтении которой воспринимается лишь первая буква(эта буква стирается, а остальная часть слова поднимается на одну ячейку). При записи в магазин слова ώ длины m( т.е. | ώ | = m ), цепочка , записанная там, двигается на m ячеек вниз, а в освободившиеся ячейки записываются символы слова ώ. Иллюстрацией сказанного может быть схема:




Работа приведенного стека символически можно записать так:

ВАС→ аВАС→ ВаВАС→ аВАС →ВАС

Замечание. Пустому стеку соответствует пустая цепочка

б) Неформальное определение МП – автоматов.

Структуру магазинного преобразователя составляют:

  1. конечный управляющий автомат

  2. три магазина – входной, внутренний и выходной.

  3. три канала, связывающие управляющий автомат с магазинами.

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





Множество состояний Q управляющего автомата разбито на два подмножества Q1 и Q2. Если состояние управляющего автомата принадлежит к подмножеству Q1, то происходит считывание из входного и внутреннего магазина.

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

Примечание. Акцептор ( распознающий МП – автомат) не имеет выходной ленты, а порождающий МП – автомат не имеет входной ленты.

Пусть A,Z,B – алфавит соответственно входного, внутреннего и выходного магазинов, не содержащие пустых букв, тогда функционирование МП – преобразователя можно представить выражениями:



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

в) Формальное определение МП – акцептора.

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

А – алфавит входных (терминальных) символов;

Q – множество состояний;

Z – конечный алфавит, состоящий из терминальных и нетерминальных символов(при этом

Δ – функция переходов МП – автоматов

, здесь - булеан, т.е. множество подмножеств ;

q0 – начальное состояние акцептора, ;

z0 - маркер внутреннего стека, ;

F – множество конечных состояний, .

Конфигурация МП – автомата описывается тройкой , где q – текущее состояние акцептора, α – цепочка непрочитанных терминальных символов на входной ленте, ώ - цепочка символов во внутреннем стеке. Такт работы перехода МП – автомата описывается в виде , если , в приведенном выражении .

Начальная конфигурация МП – автомата определяется как , а множество его конечных конфигураций МП – автомат допускает цепочку α символов входной ленты, если находясь в начальной конфигурации он может перейти в одну из конечных конфигураций . В противном случае входная цепочка не принимается.

Пример. Последовательность конфигураций МП – автомата принимающего арифметическое выражение , согласно продукциям , представим таблицей:

КОНФИГУРАЦИИ.


Дерево вывода

Состояние q

Входное слово α

Содержимое стека

q1=q0

a(b+c)

z0





q2

a(b+c)

Jz0

q2

a(b+c)

Tz0

q2

a(b+c)

TFz0

q2

a(b+c)

FFz0

q2

a(b+c)

aFz0

q2

(b+c)

Fz0

q2

(b+c)

Fz0

q2

(b+c)

(J)z0

q2

b+c)

J)z0

q2

b+c)

J+T)z0

q2

b+c)

T+T)z0

q2

b+c)

F+T)z0

q2

b+c)

b+T)z0

q2

+c)

+T)z0

q2

c)

T)z0

q2

c)

F)z0

q2

c)

c)z0

q2

)

)z0

q2

а0

z0

q3=q2

а0





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

Теорема. Классы КС – языков и языков, допускаемых МП – автоматами, совпадают.



otchyot-o-pribilyah-i-ubitkah-za-god-zakonchivshijsya-31-dekabrya-2007-goda-5-otchyot-ob-izmeneniyah-v-sobstvennom-kapitale-za-god-zakonchivshijsya-31-dekabrya-2007-goda-6-stranica-6.html
otchyot-o-pribilyah-i-ubitkah-za-god-zakonchivshijsya-31-dekabrya-2008-goda-kommercheskogo-banka-novij-vek.html
otchyot-o-prodelannoj-rabote-predmetnoj-nedeli-po-geografii-biologii-i-prirodovedeniyu-uchitelya-i-s-livonenkovoj.html
otchyot-o-prohozhdenii-proizvodstvennoj-praktiki-rabota-v-stacionare.html
otchyot-o-proshedshih-meropriyatiyah-posvyashennih-100-letiyu-sgu-4-obsheuniversitetskie-meropriyatiya-posvyashennie-100-letiyu-sgu-4.html
otchyot-o-provedenii-nedeli-detskoj-knigi-bibliotekoj-mediacentrom-mou-sosh-19-v-2010-godu.html
  • college.bystrickaya.ru/32-nalogovoe-planirovanie-putem-vibora-alternativnoj-sistemi-nalogooblozheniya.html
  • education.bystrickaya.ru/3-vmesto-zaklyucheniya-neobhodimost-prekrasheniya-szhiganiya-othodov-alternativnie-puti-resheniya-problemi.html
  • lecture.bystrickaya.ru/4-opisanie-i-rabota-sistemi-mokrogo-hraneniya-rekonstrukciya-i-tehnicheskoe-perevooruzhenie-predpriyatiya-dlya-obespecheniya.html
  • tetrad.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplini-tovarovedenie-i-ekspertiza-vkusovih-tovarov.html
  • books.bystrickaya.ru/chast-ostrova-i-zasipal-peplom-cvetushie-goroda-na-nem-no-i-nanes-ogromnij-usherb-v-n-ivanov-tajni-gibeli-civilizacij.html
  • tests.bystrickaya.ru/mdou-detskij-sad-23-kolokolchik-s-chusovitino-bank-ucheta-detej-dlya-predostavleniya-mest-v-municipalnih-doshkolnih.html
  • thesis.bystrickaya.ru/pravila-zemlepolzovaniya-i-zastrojki-bogashevskogo-selskogo-poseleniya-tomskogo-rajona-tomskoj-oblasti-primenitelno-k-chasti-territorii-poseleniya-mkr-anikino.html
  • universitet.bystrickaya.ru/tema-14-organizaciya-reklamnoj-deyatelnosti-uchebno-metodicheskij-kompleks-rekomendovano-redakcionno-izdatelskim.html
  • pisat.bystrickaya.ru/tablica-7-raschet-stoimostnoj-ocenki-godovogo-prirodoohrannogo-effekta-ot.html
  • obrazovanie.bystrickaya.ru/problemi-zakonnosti-ponyatie-principi-garantii.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-na-2011-2012-uchebnij-god-1-klassi-stranica-9.html
  • lecture.bystrickaya.ru/54cap-otdel-kadrov-joblcard-ru-obshie-voprosi-lcardlcard-ru.html
  • holiday.bystrickaya.ru/o-prepodavanii-tehnologii-2010-2011-uchebnom-godu-normativno-pravovie-dokumenti-prepodavanie-predmeta-v-2010-2011-uchebnom-godu.html
  • school.bystrickaya.ru/gotichne-rozumnnya-krasi.html
  • znanie.bystrickaya.ru/aventyura-xxi-o-tom-kak-krimhilda-ehala-k-gunnam-v-g-admoni-pesn-o-nibelungah.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-disciplina-teplotehnika-naimenovanie-disciplini-soglasno-uchebnomu-planu-stranica-2.html
  • znanie.bystrickaya.ru/4-rejting-kso-metodika-s-n-smirnov-gosudarstvo-i-modernizaciya.html
  • studies.bystrickaya.ru/izderzhki-obrasheniya-v-sovremennoj-sisteme-upravleniya-torgovim-predpriyatiem.html
  • lektsiya.bystrickaya.ru/pri-uchastii-dmitriya-bedareva-stranica-3.html
  • knowledge.bystrickaya.ru/o-v-kononova-vladivostokskij-gosudarstvennij-universitet-ekono-stranica-14.html
  • kolledzh.bystrickaya.ru/a-kucherena-prizval-glavu-mosgorsuda-podat-v-otstavku-novosti-rbk-on-line-smi-moskva-10-03-2011-17-stranica-23.html
  • tetrad.bystrickaya.ru/vnutrifrakcionnaya-rabota-radio-gosduma-rf-monitoring-smi-12-dekabrya-2006-g.html
  • lektsiya.bystrickaya.ru/postanovlenie-optimiziruet-process-provedeniya-rassledovaniya-predshestvuyushego-vvedeniyu-specialnih-zashitnih-mer-antidempingovih-mer-ili-kompensacionnih-mer.html
  • composition.bystrickaya.ru/perevod-s-franc-a-a-veselovskogo.html
  • uchenik.bystrickaya.ru/kriminalisticheskaya-harakteristika-dtp-chast-4.html
  • nauka.bystrickaya.ru/urok-v-forme-poznavatelno-intellektualnoj-igri-umniki-i-umnici.html
  • textbook.bystrickaya.ru/issledovanie-strukturi-sistemi-peredachi-informacii-i-modelirovanie-razlichnih-tipov-signalov.html
  • education.bystrickaya.ru/247-zashita-peredachi-dannih-data-line-security-rukovodstvo-po-programmirovaniyu-soderzhanie-istoriya-izmenenij.html
  • lesson.bystrickaya.ru/rok-akademicki-stranica-48.html
  • predmet.bystrickaya.ru/sostoyalis-peregovori-kuzbasskih-predprinimatelej-s-predstavitelyami-delovih-krugov-severo-kazahstanskoj-oblasti-sko.html
  • pisat.bystrickaya.ru/torgovie-nacenki-i-skidki.html
  • predmet.bystrickaya.ru/rm-rilke-otchet-po-individualnomu-issledovatelskomu-proektu-07-01-178-vipolnennomu-pri-podderzhke-nauchnogo-fonda-gu-vshe.html
  • reading.bystrickaya.ru/llektiva-prioritetnimi-ostayutsya-napravleniya-grazhdansko-patrioticheskogo-i-duhovno-nravstvennogo-stanovleniya-lichnosti-rebenka-visokaya-trebovatelnost-k-urovn.html
  • notebook.bystrickaya.ru/i-nauchno-obrazovatelnij-kompleks-tehnologii-izucheniya-osvoeniya-prognozirovaniya-i-upravleniya-georesursami-i-geosistemami.html
  • learn.bystrickaya.ru/glava-11-registraciya-tehnicheskoe-osvidetelstvovanie-i-razreshenie-na-ekspluataciyu.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.