Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Магазинные автоматы (автомат с магазинной памятью)

Магазинные автоматы (автомат с магазинной памятью)


Автоматы с магазинной памятью, или магазинные автоматы (сокращенно — МП-автоматы), образуют класс распознающих моделей для КС-языков точно так же, как конечные автоматы являются распознающими моделями в классе регулярных языков.


Понятие МП-автомата является частным случаем общего интуитивного понятия автомата, которое мы ввели ранее. Как и всякий автомат, МП-автомат — это устройство, имеющее блок управления, входную ленту, головку и блок внутренней памяти в виде магазина МП-автомата (или стека).


Блок управления в каждый момент времени находится в одном из конечного множества Q состояний.


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


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


Входной алфавит МП-автомата

Предполагается, что если на ленте записана некоторая непустая цепочка x=x(1)x(2)\ldots x(k) во входном алфавите, то ее символы последовательно записаны в ячейках от первой до k-й, без пропусков, так, что символ x(i) записан в i-й ячейке (рис. 8.29).


Входной алфавит МП-автомата 2

МП-автомат может читать цепочку x, продвигая головку только в одном направлении, слева направо, по шагам, причем за каждый шаг головка переходит от обозреваемой ячейки к следующей. Если в какой-то момент времени обозревается символ x(i),~1\leqslant i\leqslant k, записанной на ленте цепочки x, то непрочитанной частью входной цепочки x будет подцепочка x(i+1)\ldots x(k). В частности, при i=k непрочитанная часть совпадает с пустой цепочкой, и тогда говорят, что цепочка x полностью прочитана МП-автоматом (рис. 8.30).


3. Входной алфавит МП-автомата



Устройство и работа магазина МП-автомата


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


*Таким образом, в неформальном описании МП-автомата лента читается "слева направо", а магазин — "сверху вниз".


Единственная операция, которую МП-автомат может реализовать с магазином, состоит в следующем: верхний символ Z магазина заменяется некоторой цепочкой \gamma магазинных символов. При этом если цепочка \gamma непустая, то она записывается в первых m ячейках, где m=|\gamma| (длине цепочки \gamma), так, что ее первый символ становится верхним символом магазина.


Если до замены Z цепочкой \gamma под верхней ячейкой** (т.е. в ячейках, начиная со второй) была записана какая-то цепочка а, то после замены она сдвигается "в глубь" магазина и оказывается записанной уже в ячейках, начиная с (m+1)-й (рис. 8.31).


Операция, которую МП-автомат может реализовать с магазином

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


Если же верхний символ Z заменяется пустой цепочкой \lambda, то после такой замены верхним символом магазина становится первый символ цепочки \alpha (записанной под верхней ячейкой магазина), т.е. цепочка \alpha "поднимается" на одну ячейку.


В случае, когда \alpha — пустая цепочка, замена верхнего символа магазина пустой цепочкой \gamma приводит к опустошению магазина (ни в одной из ячеек магазина не записан магазинный символ). Заметим, что, по определению, с пустым магазином МП-автомат не может производить никаких операций.


Описанная выше операция с магазином составляет основу поведения МП-автомата, его, образно говоря, "динамику". Эта "динамика" определяется системой команд МП-автомата, которая, аналогично системе команд конечного автомата, определяется как конечное множество \delta команд, каждая из которых записывается в виде


qaZ\to r\gamma,
(8.8)

где q и r — состояния из множества Q; a — входной символ или пустая цепочка; Z — магазинный символ; \gamma — цепочка магазинных символов (может быть и пустая).


Если в системе команд \delta МП-автомата M есть команда (8.8), то M может в данный момент времени выполнить эту команду, если и только если в данный момент времени его блок управления находится в состоянии q, головка обозревает входной символ a (при условии, что a\ne\lambda), а верхним символом магазина является символ Z. Выполнение команды (8.8) состоит в замене верхнего символа магазина цепочкой \gamma (как это описано выше), переходе блока управления в состояние r (которое может и совпадать с состоянием q) и в продвижении головки на одну ячейку вправо (если а в команде (8.8) не есть пустая цепочка \lambda) (рис. 8.32).


Система команд МП-автомата

Если же в команде (8.8) a=\lambda, то такую команду МП-автомат может выполнить всякий раз, когда его блок управления окажется в состоянии q, а верхним символом магазина будет символ Z. В этом случае выполнение команды никак не зависит от содержимого входной ленты, а после ее выполнения головка остается на прежнем месте.


Рассмотренную выше процедуру выполнения команды вида (8.8) называют шагом (или тактом) работы МП-автомата (при a=\lambda такт работы называют λ-тактом).


Предположим теперь, что в множестве состояний Q блока управления МП-автомата M с системой команд \delta фиксировано некоторое начальное состояние q_0 и подмножество заключительных состояний F.


Пусть в какой-то начальный момент времени блок управления МП-автомата M находится в начальном состоянии q_0, налейте записана непустая цепочка x, головка обозревает первую ячейку ленты и, следовательно, первый символ цепочки x является обозреваемым, а в магазине записан только один специальный символ Z_0, называемый начальным символом магазина.


Тогда, если МП-автомат M, выполняя некоторую последовательность команд из \delta, прочитывает полностью цепочку x, в результате чего блок управления переходит в некоторое заключительное состояние q_f\in F, говорят, что МП-автомат M допускает (распознает, воспринимает) цепочку x, которую называют допустимой цепочкой МП-автомата. Множество всех допустимых цепочек МП-автомата M образует язык, допускаемый этим МП-автоматом.


Далее мы докажем, что язык любого МП-автомата является КС-языком и, наоборот, любой КС-язык есть язык некоторого МП-автомата. В этом смысле мы и говорим об МП-автоматах как о "распознавателях" КС-языков: всякий МП-автомат допускает те и только те цепочки входных символов, которые порождаются некоторой КС-грамматикой. Но чтобы доказывать какие-либо утверждения об МП-автоматах, нужно сначала дать строгое математическое определение этого понятия, не апеллируя уже к наглядным, но не определенным формально идеям ленты, магазина, головки и т.п. Формализация изложенного выше описания проводится во многом аналогично построению определения порождающей грамматики.




Определение 8.7. МП-автомат задается упорядоченной семеркой


M=(Q,V,\Gamma,q_0,F,Z_0,\delta),

где Q — конечное множество состояний; V — алфавит, называемый входным алфавитом; \Gamma — алфавит, называемый магазинным алфавитом; q_0\in Q — начальное состояние; F\subseteq Q — подмножество заключительных состояний; Z_0\in\Gamma — начальный магазинный символ; \delta — система команд, определенная как конечное множество команд, каждая из которых записывается в виде (8.8): qaZ\to r\gamma, где знак "\to" (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов);


q,r\in Q;\qquad a\in V\cup\{\lambda\};\qquad Z\in\Gamma;\qquad \gamma\in \Gamma^{\ast}.

Замечание 8.8. Нелишне обратить внимание на то, что упоминание о ленте и магазине в приведенном выше формальном определении совершенно необязательно. Формально для определения МП-автомата достаточно задать два алфавита, конечное множество состояний, выделив в нем начальное состояние и подмножество заключительных состояний, а также систему команд. Образы ленты, магазина, да и сам термин "состояние", являются метафорами, которые позволяют связать формальное определение с его содержательной интерпретацией, идеей некоего "устройства" для чтения слов, с описания которого мы начали этот параграф.


Любую цепочку в алфавите V будем называть входной цепочкой, а сами элементы входного алфавита — входными символами; точно так же любую цепочку в алфавите \Gamma будем называть магазинной цепочкой, а символы этого алфавита — магазинными символами. Упорядоченную тройку до знака "\to" (стрелки) в записи команды называют левой частью команды, а упорядоченную пару после знака "\to" — правой частью команды.




Пример 8.14. Рассмотрим МП-автомат M_1=(\{q_0,q_1,q_2\}, \{0;1\}, \{Z,0\}, q_0, \{q_0\},Z,\delta_1) с таким множеством команд \delta_1\colon


q_00Z\to q_1\,0Z,\quad q_000\to q_1\,00,\quad q_110\to q_2\lambda,\quad q_210\to q_2\lambda,\quad q_2\lambda Z\to q_0\lambda.

На рис. 8.33 проиллюстрировано выполнение первых двух команд. При записи системы команд этого конкретного МП-автомата мы в правых частях первых двух команд отделили магазинную цепочку от состояния пробелом для того, чтобы не возник соблазн прочитать левую и правую части этих команд одинаково. Таким приемом записи мы хотим подчеркнуть, что левая часть команды МП-автомата — упорядоченная! тройка, а правая — упорядоченная пара.


Выполнение команд МП-автомата

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


\delta\colon Q\times(V\cup\{\lambda\})\times\Gamma\to \mathbf{Fin}(Q\times \Gamma^{\ast}),

где использовано обозначение \mathbf{Fin}(A) для множества всех конечных подмножеств множества A.


"Динамику" МП-автомата, т.е. процесс перехода его из одного состояния в другое в соответствии с обозреваемыми символами на ленте и содержимым магазина, удобнее всего описывать в терминах конфигураций. Для этого общее понятие конфигурации автомата, которое на интуитивном уровне было введено в 7.5, необходимо уточнить применительно к МП-автомату и определить также отношение выводимости на множестве конфигураций.




Определение 8.8. Конфигурацией МП-автомата M называют упорядоченную тройку вида (q,x,\beta), где q\in Q — состояние, x\in V^{\ast} — входная цепочка, \beta — магазинная цепочка.


Конфигурацию C'=(r,w,\gamma\alpha) называют непосредственно выводимой из конфигурации C=(q,aw,Z\alpha), если в множестве команд МП-автомата есть команда (8.8). Отношение непосредственной выводимости на множестве конфигураций МП-автомата M обозначаем \vdash_M, используя запись C\vdash_{M}C' (и опуская, если это не вредит пониманию, обозначение самого МП-автомата).


Итак, непосредственная выводимость

(q,aw,Z\alpha)\vdash_{M}(r,w,\gamma\alpha)
(8.9)

имеет место тогда и только тогда, когда в системе \delta команд МП-автомата M есть команда (8.8), которую в этом случае называют применимой к конфигурации (q,aw,Z\alpha).


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


На рис. 8.33 изображены (в терминах приведенного выше содержательного описания) две конфигурации МП-автомата из примера 8.14, причем вторая конфигурация непосредственно выводится из первой. Понятие непосредственной выводимости, таким образом, формализует данное выше понятие такта '(или шага) работы МП-автомата. Заметим, что если в (8.9) и в команде (8.8) a=\lambda, т.е. имеет место λ-такт, то команда (8.8) применима к любой конфигурации, у которой (говоря неформально) состояние блока управления есть q, а верхний символ магазина — Z, причем, подчеркнем это, независимо от содержимого входной ленты (т.е. для любой входной цепочки w). Если же a есть входной символ, то применимость команды к конфигурации определяется состоянием, обозреваемым символом на ленте и верхним символом магазина.


Любую конфигурацию вида (q_0,x,Z_0) называют начальной, а любую конфигурацию вида (q_f,\lambda,\lambda), где q_f\in F, — заключительной. Обратим внимание на то, что заключительная конфигурация — это конфигурация с пустым магазином. Множество всех заключительных конфигураций находится, таким образом, во взаимно однозначном соответствии с множеством заключительных состояний МП-автомата. Из заключительной конфигурации не может быть выведена ни одна конфигурация, так как к ней не применима ни одна команда. Конфигурацию МП-автомата, не являющуюся заключительной и к которой не применима ни одна команда, называют тупиковой.




Определение 8.9. Выводом на множестве конфигураций МП-автомата M называют последовательность C_0,C_1,\ldots,C_n,\ldots (конечную или бесконечную) таких его конфигураций, что для любого i\geqslant0 имеет место C_i\vdash C_{i+1}, если C_{i+1} существует.


Если вывод конечен и C_n — его последняя конфигурация, то число n называют длиной вывода. В этом случае будем говорить, что вывод C_0,C_1,\ldots,C_n связывает конфигурацию C_0 с конфигурацией C_n.


Конфигурацию C' называют выводимой из конфигурации C, обозначая это как C\vdash^{\ast}C', если существует вывод, связывающий C с C', т.е. вывод C_0,C_1,\ldots,C_n такой, что C_0=C, а C_n=C'.


В частности, при n=0 получаем, что любая конфигурация выводится сама из себя; при n=1 получаем непосредственную выводимость C' из C. В общем случае говорят, что конфигурация C' выводится из конфигурации C за n шагов, записывая при этом C\vdash^nC'. Желая подчеркнуть, что существует вывод ненулевой длины конфигурации C' из конфигурации C, то есть C\vdash^nC и n>0, записывают C\vdash^{+}C'.


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




Строгое определение языка МП-автомата


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


Определение 8.10. Входную цепочку x называют допустимой цепочкой МП-автомата M (см. определение 8.7), если на множестве конфигураций M существует вывод, связывающий начальную конфигурацию (q_0,x,Z_0) с заключительной конфигурацией (q_f,\lambda,\lambda), где q_f\in F, то есть


(q_0,x,Z_0)\vdash_{M}^{\ast}(q_f,\lambda,\lambda).

Язык, допускаемый МП-автоматом M (или просто язык МП-автомата M), — это множество всех его допустимых цепочек.


МП-автоматы M_1 и M_2 называют эквивалентными, если их языки совпадают, т.е. L(M_1)=L(M_2).


Любой вывод на множестве конфигураций МП-автомата, связывающий начальную конфигурацию С C_0^x=(q_0,x,Z_0) с одной из заключительных, называют допускающей последовательностью конфигураций для цепочки x. Цепочка x принадлежит языку L(M) тогда и только тогда, когда для нее существует допускающая последовательность конфигураций. Тем не менее может оказаться так, что даже в том случае, когда x\in L(M), из начальной конфигурации C_0^x можно вывести отнюдь не только заключительную конфигурацию.




Пример 8.15. Пусть МП-автомат M=(\{q_0,q_1,q_2\},\{a,b\},\{Z,a,b\}, q_0,\{q_0\}, Z,\delta_2) определен множеством команд \delta_2\colon


\begin{array}{lrlrlr}q_0aZ\to q_0aZ,&\quad (1)&\qquad q_0ab\to q_0ab,&\quad (5)&\qquad q_1aa\to q_1\lambda,&\quad (9)\\q_0bZ\to q_0bZ,&\quad (2)&\qquad q_0ba\to q_0ba,&\quad (6)&\qquad q_1bb\to q_1\lambda,&\quad (10)\\ q_0aa\to q_0aa,&\quad (3)&\qquad q_0bb\to q_0bb,&\quad (7)&\qquad q_1\lambda Z\to q_2\lambda.\\ q_0aa\to q_0\lambda,&\quad (4)&\qquad q_0bb\to q_1\lambda,&\quad (8)&\qquad &\quad (11){}&{} \end{array}

Можно доказать, что этот МП-автомат допускает зеркальный язык \{xx^R\in \{a,b\}^{\ast}\}, где x^R обозначает инверсию цепочки x.


Приведем допускающую последовательность конфигураций для цепочки abba:


\begin{aligned}(q_0,abba,Z)&\vdash_{(1)} (q_0,bba,aZ)\vdash_{(6)} (q_0,ba,baZ)\vdash_{(8)}\\ &\vdash_{(8)} (q_1,a,aZ)\vdash_{(9)} (q_1,\lambda,Z)\vdash_{(11)} (q_2,\lambda,\lambda)\end{aligned}

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


К начальной конфигурации (q_0,abba,Z) применима только команда (1). После выполнения этой команды первый символ входной цепочки будет прочитан, а в магазине вместо одного символа Z окажется цепочка aZ, т.е. символ а станет верхним символом магазина.


К полученной конфигурации (q_0,bba,aZ)применима только команда (6), в результате выполнения которой будет прочитан еще один символ входной цепочки, т.е. ее второй символ b, ив магазине окажется цепочка baZ.


К третьей конфигурации записанного выше вывода применимы две команды: (7) и (8). Выбирая команду (8), мы тем самым читаем третий символ входной цепочки, а верхний символ магазина, совпавший с указанным символом входной цепочки, "выталкиваем" из магазина, после чего верхним символом магазина окажется уже символ а, т.е. возникнет конфигурация (q_1,a,aZ). Заметим также, что после выполнения команды (8) МП-автомат M_2 окажется в новом состоянии q_1.


Применив к конфигурации (q_1,a,aZ) единственную применимую к ней команду (9), получим конфигурацию (q_1,\lambda,Z), т.е. входная цепочка прочитана полностью, а в магазине остался символ Z.


Применяя опять-таки единственно возможную для такой конфигурацию команду (11), мы убираем символ Z из магазина, тем самым опустошая его, и переходим в заключительное состояние q_2.


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


(q_0,ba,baZ)\vdash_{(7)} (q_0,a,bbaZ)\vdash_{(5)} (q_0,\lambda,abbaZ).

Последняя конфигурация в этом выводе характеризуется тем, что входная цепочка прочитана, магазин не пуст, состояние не является заключительным и не применима ни одна команда, т.е. полученная конфигурация (q_0,\lambda,abbaZ) МП-автомата M_2 является тупиковой.




Рассмотренный пример показывает, что МП-автомат может попасть в тупиковую конфигурацию, читая даже "правильную" цепочку, т.е. цепочку, принадлежащую его языку. Это связано с недетерминированностью МП-автомата, т.е. с тем, что из данной конфигурации можно непосредственно вывести, вообще говоря, более чем одну конфигурацию*. Тот факт, что входная цепочка принадлежит языку МП-автомата, означает лишь, что существует допускающая последовательность конфигураций для этой цепочки, но не всякая последовательность конфигураций, которая возникает при чтении этой цепочки, будет допускающей. Задача эффективного поиска допускающей последовательности конфигураций — одна из основных задач разработки алгоритмов синтаксического анализа на базе МП-автоматов.


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


Как уже отмечалось, основное свойство языков, допускаемых МП-автоматами, состоит в том, что эти языки образуют класс, совпадающий с классом КС-языков. Но перед тем как доказывать этот основной результат теории МП-автоматов, аналогичной теореме Клини для конечных автоматов, установим одно весьма полезное свойство МП-автомата, состоящее в том, что "хвост" входной цепочки и "дно" магазина не влияют на работу МП-автомата с началом входной цепочки и верхом магазина, так как входная цепочка читается строго символ за символом без возвратов и забеганий вперед, а магазин обновляется только сверху.


Приведем строгую формулировку.


Теорема 8.5. Пусть в МП-автомате M=(Q,V,\Gamma,q_0,F,Z_0,\delta) на множестве конфигураций для некоторых q,r\in Q,~x,y\in V^{\ast} и \alpha,\beta\in \Gamma^{\ast} имеет место выводимость


(q,xy,\alpha)\vdash_{M}^{\ast}(r,y,\beta).
(8.10)

Тогда для произвольных z\in V^{\ast},~\gamma\in\Gamma^{\ast} имеет место выводимость


(q,xyz,\alpha\gamma)\vdash_{M}^{\ast}(r,yz,\beta\gamma).
(8.11)

Обратно, если для некоторых q,r\in Q,~x,y,z\in V^{\ast} и \alpha,\beta,\gamma\in \Gamma^{\ast} имеет место выводимость (8.11), то выполняется и выводимость (8.10).


Индукцией по длине вывода, связывающего конфигурацию (q,xy,\alpha) с конфигурацией (r,y,\beta) в (8.10) докажем, что если эта выводимость имеет место, то имеет место и выводимость (8.11). Для вывода нулевой длины утверждение тривиально.


Пусть доказываемое верно для любой длины вывода, связывающего конфигурации в (8.10), не превышающей n-1. Предположим, что (q,xy,\alpha)\vdash_{M}^{n} (r,y,\beta). Рассмотрим первый шаг соответствующего вывода. Пусть он имеет вид


(q,ax'y,Z\alpha')\vdash_{M} (q',x'y,\sigma\alpha'), где x=ax',~ \alpha= Z\alpha',~a\in V\in\{\lambda\} и Z\in\Gamma.

Это значит, что на этом шаге применена команда

qaZ\to q'\sigma.
(8.12)

Согласно предположению индукции, для произвольных z\in V^{\ast} и \gamma\in\Gamma^{\ast} имеет место выводимость


(q',x'yz,\sigma\alpha'\gamma)\vdash^{n-1}(r,yz,\beta\gamma).
(8.13)

Рассмотрим конфигурацию (q,xyz,\alpha\gamma)=(q,ax'yz,Z\alpha'\gamma) и применим к ней команду (8.12). Получим


(q,ax'yz,Z\alpha'\gamma)\vdash_{M} (q',x'yz,\sigma\alpha'\gamma).

Отсюда в силу (8.13), будем иметь

(q,ax'yz,Z\alpha'\gamma)\vdash (q',x'yz,\sigma\alpha'\gamma)\vdash_{M}^{n-1}(r,xy,\beta\gamma),

т.е. при выводимости (8.10) за n шагов имеет место и выводимость (8.11) также за n шагов, что и требовалось доказать.


Аналогично (но уже индукцией по длине вывода (8.11)) доказывается, что если имеет место выводимость (8.11), то имеет место и выводимость (8.10).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved