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

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

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

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


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

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


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


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

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


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


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

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


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

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




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


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


e_1,\,\underbrace{e_2,\ldots,e_2}_{m~\text{times}},\, \underbrace{e_3,\ldots, e_3}_{m~\text{times}}.

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


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


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

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


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


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\,.

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


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

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


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

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


\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}

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


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


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


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

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

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


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

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