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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


Графовое представление МП-автоматов

Графовое представление МП-автоматов


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


[math]M=(Q,\,V,\,\Gamma,\,q_0,\,F,\,Z_0,\,\delta)[/math]

сопоставляется ориентированный мультиграф (в отличие от обычного ориентированного графа в мультиграфе допускается несколько дуг для одной и той же упорядоченной пары вершин, т.е. несколько дуг, начало и конец которых совпадают), множество вершин которого есть множество состояний автомата, а каждая дуга которого имеет метку в виде упорядоченной тройки [math](Z,a,\gamma)[/math], где [math]Z[/math] — магазинный символ, [math]a[/math] — входной символ или пустая цепочка, [math]\gamma[/math] — магазинная цепочка. По определению, дуга [math]e[/math], ведущая из вершины (состояния) [math]q[/math] в вершину (состояние) [math]r[/math] имеет метку [math](Z,a,\gamma)[/math], если и только если в системе команд [math]\delta[/math] находится команда [math]qaZ\to r\gamma[/math].


Замечание 8.16. Более формально ориентированный мультиграф может быть определен как упорядоченная тройка [math]G=(V,E,\varphi)[/math], где [math]V[/math] — множество вершин, [math]E[/math] — множество дуг, а [math]\varphi[/math] — отображение множества [math]E[/math] в множество [math]V\times V[/math], называемое функцией инцидентности. Таким образом, если для различных дуг [math]e_1,\ldots,e_k[/math] все значения [math]\varphi(e_1), \ldots,\varphi(e_1)[/math] равны, то возникает "множественная", или "кратная", дуга, т.е. множество дуг, отображаемых в одну и ту же упорядоченную пару вершин [math](u,v)[/math]. Графически это можно изобразить так, как показано на рис. 8.40. В том случае, когда функция инцидентности есть инъекция, мультиграф превращается в обычный ориентированный граф.


Множество дуг, отображаемых в одну и ту же упорядоченную пару вершин

В мультиграфе, представляющем МП-автомат, множество дуг для заданной упорядоченной пары состояний [math](q,r)[/math] находится во взаимно однозначном соответствии с множеством всех команд [math]qaZ\to r\gamma[/math] для различных


[math]a\in V\cup\{\lambda\},\qquad Z\in\Gamma,\qquad \gamma\in\Gamma^{\ast}.[/math]

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




Магазинная метка пути в мультиграфе МП-автомата


Введем понятие магазинной метки пути в мультиграфе МП-автомата. Для этого заметим, что понятие пути в мультиграфе слегка отличается от такового в обычном ориентированном графе. Под путем в мультиграфе понимается произвольная последовательность дуг [math]e_1,e_2,\ldots, e_n,\ldots[/math], где [math]n\geqslant1[/math], такая, что любая пара соседних дуг [math]e_i,e_{i+1}[/math] этой последовательности смежна, т.е. существует вершина [math]q_{i+1}[/math], в которую дуга [math]e_i[/math] заходит и из которой дуга [math]e_{i+1}[/math] выходит. Число дуг в пути (для конечного пути) назовем его длиной. Пути в мультиграфе будем записывать как цепочки в алфавите [math]E[/math]: так, запись [math]e_1e_2^me_3^n[/math] обозначает путь, являющийся последовательностью дуг


[math]e_1,\,\underbrace{e_2,\ldots,e_2}_{m~\text{times}},\, \underbrace{e_3,\ldots, e_3}_{m~\text{times}}.[/math]

Тогда магазинная метка дуги (т.е. пути длины 1) с меткой [math](Z,a,\gamma)[/math] есть цепочка [math]\gamma[/math]; магазинная метка пути [math]e_1,e_2,\ldots,e_n[/math] длины [math]n[/math] при условии, что магазинная метка пути [math]e_1,e_2,\ldots,e_{n-1}[/math], служащего началом исходного пути, определена и равна [math]\gamma[/math], а дуга [math]e_n[/math] имеет метку [math](Y,b,\alpha)[/math], равна [math]\alpha(Y^{-1}\gamma)[/math]. Напомним, что для произвольных алфавита [math]W[/math], его буквы [math]a[/math] и цепочки [math]x[/math] в алфавите [math]W[/math] выражение [math]a^{-1}x[/math] означает цепочку [math]y[/math], такую, что [math]ay=x[/math], и не определено, если первая буква цепочки [math]x[/math] отлична от [math]a[/math] (см. задачу 7.23). Таким образом, магазинная метка пути в мультиграфе, представляющем МП-автомат, может быть не определена.


Введем операцию Y-сцепления магазинных меток двух. смежных дуг [math]e_1[/math] и [math]e_2[/math] с метками [math](Z,a,\gamma)[/math] и [math](Y,b,\alpha)[/math] соответственно, полагая [math]\gamma\otimes_{Y} \alpha= \alpha Y^{-1}\gamma[/math] (рис. 8.41).


Y-сцепления магазинных меток двух смежных дуг

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


Рассмотрим в качестве примера МП-автомат для языка [math]L=\{a^nb^n\colon n\geqslant0\}[/math]. Его система команд имеет следующий вид:


[math]q_0aZ\to q_0aZ,\quad q_0aa\to q_0aa,\quad q_0ba\to q_1\lambda,\quad q_1ba\to q_1\lambda,\quad q_1\lambda Z\to q_2\lambda\,.[/math]

По этой системе команд строим мультиграф (рис. 8.42 ).


Пример мультиграфа

Ясно, что дуга с меткой [math](Z,a,aZ)[/math] не может быть сцеплена сама с собой, так как выражение [math]aZ\otimes_{Z}aZ=aZ(Z^{-1}aZ)[/math] не определено. Но верхняя петля в начальной вершине может сцепиться с нижней, а последняя сцепляется сама с собой. Например,


[math]\begin{aligned}aZ\otimes_{a}aa&= aa(a^{-1}aZ)=aaZ,\\[2pt] aaZ\times_{a}aa&= aa(a^{-1}aaZ)=aaaZ.\end{aligned}[/math]

Неформально любой путь [math]e_1e_2^{n-1}[/math] соответствует переписыванию с ленты в магазин [math]n[/math] символов [math]a[/math]. Тогда путь [math]e_1e_2^{n-1}e_3e_4^{n-1}e_5[/math] имеет входную метку [math]a^nb^n[/math] и магазинную метку [math]\lambda[/math]. Так, для цепочки [math]aaabb[/math] будем иметь последовательность сцеплений:


[math]\begin{aligned}&((((((aZ\otimes_{a}aa) \otimes_{a} aa) \otimes_{a}\lambda) \otimes_{a}\lambda) \otimes_{a}\lambda) \otimes_{Z}\lambda)=\\ &\quad =((((aaaZ\otimes_{a}\lambda) \otimes_{a}\lambda) \otimes_{a}\lambda) \otimes_{Z}\lambda)=\\ &\quad =Z\otimes_{Z}\lambda= \lambda\,.\end{aligned}[/math]

Если в цепочке больше символов [math]a[/math], чем [math]b[/math], то мы, вычисляя магазинную метку соответствующего пути, придем к выражению [math]a^k\otimes_{Z} \lambda[/math], которое не определено. Если же в цепочке больше символов [math]b[/math], чем [math]a[/math], то мы не попадем в заключительную вершину, так как в нашем мультиграфе нет дуги с меткой, первая компонента которой равна [math]Z[/math], а вторая — [math]b[/math].


Обратим внимание на то, что если мы забудем о магазинных метках и будем рассматривать наш мультиграф как граф обычного конечного автомата, то получим регулярное выражение [math]a^{\ast}b^{+}[/math]. Таким образом, вычисление магазинных меток вдоль путей мультиграфа фильтрует множество входных цепочек, допускаемых МП-автоматом, т.е. в регулярном языке выделяется подмножество более сложной структуры — некоторый КС-язык.


Любая дуга, исходящая из начальной вершины и имеющая метку [math](Z_0,a,\gamma)[/math] для произвольных [math]a\in V\cup\{\lambda\}[/math] и [math]\gamma\in\Gamma^{\ast}[/math], называется стартовой. Тогда нетрудно дать графовую интерпретацию языка МП-автомата.


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


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


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

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