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

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

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

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


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

Конечные автоматы в языках программирования


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


Пусть задана некоторая порождающая грамматика G с терминальным алфавитом V и цепочка x в алфавите V. Спрашивается: принадлежит ли цепочка x языку, порождаемому грамматикой G? Эту задачу называют проблемой принадлежности для грамматики G. В теории формальных языков доказывается, что проблема принадлежности разрешима для КЗ-грамматик и для КС-грамматик, но в общем случае не разрешима для грамматик типа 0. Решение проблемы принадлежности состоит в разработке распознающего алгоритма, который для произвольных грамматики G (из заданного класса грамматик) и цепочки x за конечное число шагов выдает ответ на поставленный выше вопрос. В основе подобного рода алгоритмов лежит математическая модель языка, называемая распознающей моделью или анализирующей моделью и являющаяся как бы зеркальной к порождающей модели, примером которой служит порождающая грамматика. Традиционно анализирующие модели языков называют автоматами. В каждом классе языков может быть определена пара порождающая модель — анализирующая модель" или, другими словами, пара "грамматика — автомат", где автомат в определенном смысле анализирует (распознает) цепочки, порождаемые грамматикой.


Неформально автомат можно описать как устройство, состоящее из блока управления, входной ленты, головки автомата и блока внутренней памяти автомата (рис. 7.2). На ленте, которая предполагается полубесконечной (не ограниченной справа) и разделена на ячейки, записываются цепочки во входном алфавите (обозначаемом далее V) так, что буквы цепочки занимают последовательно, начиная с первой и без пропусков, ячейки ленты — по одной букве в каждой ячейке. Цепочку, записанную таким образом на входной ленте автомата, будем называть входной цепочкой. Блок управления может в каждый момент времени находиться в одном из конечного множества состояний (обозначим его через Q), а головка может быть установлена в точности на одну ячейку входной ленты. В таком случае говорят, что автомат обозревает данную ячейку.


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

Автомат, читая входную цепочку, работает по шагам (или по тактам). Пусть в некоторый момент времени автомат обозревает какую-то ячейку ленты, а блок управления находится в некотором состоянии q\in Q. Такт работы автомата состоит в том, что в зависимости от содержимого обозреваемой ячейки, состояния q, а также содержимого внутренней памяти автомат сдвигает головку вправо или влево на одну ячейку либо оставляет ее на прежнем месте, его блок управления переходит в некоторое новое состояние r (возможно, что это состояние совпадет с исходным состоянием q), а содержимое внутренней памяти определенным образом модифицируется. В общем случае автомат может и поменять содержимое той ячейки ленты, которую он обозревает (т.е. автомат может работать с лентой или только в режиме чтения, не меняя ее содержимого, а лишь определенным образом продвигая головку, или в режиме чтения/записи).


Вводят понятие конфигурации автомата: она определяется состоянием блока управления, содержимым обозреваемой ячейки и содержимым внутренней памяти*. Автомат в общем случае не является детерминированным устройством, т.е. для него из заданной конфигурации возможны переходы в несколько различных конфигураций. Правила, согласно которым автомат переходит из одной конфигурации в другую, составляют в совокупности его систему команд автомата. Каждая команда разрешает переход из некоторой конфигурации в какую-то другую конфигурацию. Это напоминает игру, например шахматную, когда из текущей позиции на доске можно, сделав ход, получить новую позицию — одну из множества всех позиций, в которые можно попасть из текущей позиции, сделав ход согласно правилам игры. В данном случае правила игры аналогичны системе команд, а позиция на доске — конфигурации автомата.


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


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


Представим теперь следующую ситуацию. Пусть на входной ленте автомата записана некоторая цепочка x\in V^{\ast}. Допустим также, что среди состояний блока управления выделено некоторое специальное состояние, называемое начальным, а также некоторое подмножество состояний, которые называются заключительными.


В начальный момент времени блок управления находится в начальном состоянии, головка обозревает первую (крайнюю левую) ячейку ленты, в которой записан первый символ входной цепочки x. Читая цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q' (точнее говоря, в этом состоянии окажется блок управления). Если это состояние является заключительным, то тогда говорят, что автомат допустил цепочку x. Спрашивается: каким образом посредством грамматики можно описать множество всех цепочек в алфавите V, которые автомат допускает?


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


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


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


Итак, из каждого состояния автомат может переходить в другое состояние, читая тот или иной символ входной цепочки, или делать переход по пустой цепочке, причем принимается по определению, что эти два типа переходов исключают друг друга. Поведение конечного автомата определяется его системой команд, в которой каждая команда задается записью


qa\to r,
(7.4)

что означает: "из состояния q по символу a\in V или по пустой цепочке (тогда a=\lambda) можно перейти в состояние r" (возможно, что q=\lambda).


При этом по определению принимается, что переход по пустой цепочке и переход по входному символу исключают друг друга. То есть для любой пары (q,r) состояний конечного автомата имеет место следующее: если существует команда (7.4) при a=\lambda, то нет ни одной команды (для такой же пары состояний) при a\in V и наоборот.


Конфигурация конечного автомата определяется как упорядоченная пара (q,ay), где q — состояние блока управления, a — символ в обозреваемой ячейке, y — цепочка во входном алфавите, расположенная в ячейках справа от обозреваемой (цепочку ау принято называть непрочитанной частью входной цепочки). При этом если обозреваемая ячейка пуста, т.е. не содержит какого-либо символа входного алфавита, то непрочитанная часть входной цепочки считается пустой цепочкой.


Чтобы дать математическое определение конечного автомата, нужно заметить, что он, в свете только что изложенного неформального описания, допускает естественную интерпретацию в терминах размеченных ориентированных графов. Будем рассматривать состояния блока управления конечного автомата как вершины ориентированного графа, множество дуг которого определяется системой команд следующим образом: дуга ведет из состояния q в состояние r (для данных состояний q и r) тогда и только тогда, когда в системе команд автомата есть команда (7.4), т.е. возможен переход из состояния q в состояние r. Каждая дуга имеет метку, которая является либо множеством букв входного алфавита, либо пустой цепочкой.


Метка дуги (q,r) есть пустая цепочка \lambda, если из q в r можно перейти по пустой цепочке; в противном случае метка дуги (q,r) есть множество всех входных символов, по которым возможет переход из состояния q в состояние r.




Пример 7.7. Зададим конечный автомат с входным алфавитом \{a,b,c\} и множеством состояний \{q_0,q_1,q_2,q_3\} такой системой команд:


\begin{array}{lll}q_0\lambda\to q_1,&\qquad q_0\lambda\to q_3,&\qquad q_1a\to q_2,\\ q_1b\to q_2,&\qquad q_1a\to q_3,&\qquad q_2b\to q_1,\\ q_3b\to q_2,&\qquad q_3c\to q_2,&\qquad q_3c\to q_3. \end{array}

Размеченный ориентированный граф

По этой системе команд построим размеченный ориентированный граф, изображенный на рис. 7.3. Среди состояний автомата выделены начальное состояние q_0 и два заключительных состояния q_2 и q_3. На рис. 7.4 показана последовательность конфигураций, которую проходит конечный автомат, читая цепочку abac. Эту цепочку автомат допускает, так как, читая ее, он переходит из начального состояния в одно из заключительных. В формальной записи последовательность конфигураций на рис. 7.4 выглядит так:


(q_0,abac),\quad (q_1,abac),\quad (q_2,bac),\quad (q_1,ac),\quad (q_3,c),\quad (q_3,\lambda).

Этой последовательности отвечает путь в ориентированном графе, ведущий из вершины q_0 в вершину q_3:


q_9\to_{\lambda} q_1\to_{a} q_2\to_{b} q_1\to_{a} q_3\to_{c} q_3)

(под каждой стрелкой подписана буква, принадлежащая метке соответствующей дуги и являющаяся очередной буквой читаемой входной цепочки). Заметим, что, например, находясь в состоянии q_1 и обозревая второй от конца цепочки символ, т.е. символ a, автомат мог, согласно системе команд, сделать переход в состояние q_2, а не в состояние q_3, но тогда он бы "завис" в состоянии q_2 и не смог бы прочитать последний символ записанной на ленте цепочки, т.е. символ c, так как среди команд нет такой, которая разрешала бы переход из состояния q_2 куда-либо по символу c.


Последовательность конфигураций, которую проходит конечный автомат

Эта ситуация демонстрирует как раз недетерминированность конечного автомата как распознающего устройства: система команд ("правила игры") позволяет автомату допустить цепочку abac ("игроку" найти последовательность ходов, ведущую к "выигрышу"), но из этого вовсе не следует, что последовательность конфигураций, которую проходит автомат, читая записанную на ленте цепочку, является единственной. Автомат может "ошибиться", сделав "неправильный" ход. Но и последовательность "правильных" ходов может быть не единственной. Например, читая последний символ цепочки, т.е. символ c, автомат мог "выбрать" переход в состояние q_2, которое также является заключительным. Рассматриваемый автомат допускает не всякую цепочку в алфавите \{a,b,c\}. Видно, что ни одна цепочка, которая начинается с префикса ca, не будет допущена автоматом.




Обозначение пустой цепочки \lambda, фигурирующей в виде метки дуги ориентированного графа, который представляет конечный автомат, можно интерпретировать как регулярное выражение, т.е. как регулярный язык, состоящий из одной пустой цепочки (см. замечание 7.4). Поскольку метка дуги, являющаяся множеством букв \{b_1,\ldots,b_m\}\subseteq V, может быть также записана в виде регулярного выражения, а именно как сумма b_1+\ldots +b_m, то метку каждой дуги можно считать регулярным выражением определенного вида или, так как мы отождествляем регулярные языки и регулярные выражения, регулярным языком. Это позволяет нам формально определить конечный автомат как ориентированный граф, размеченный над полукольцом \mathcal{R}(V) регулярных языков. Такое математическое определение конечного автомата весьма удобно: оно дает нам возможность применить при изучении конечных автоматов уже изученные нами алгебраические методы анализа размеченных ориентированных графов.


Итак, математическое определение конечного автомата формулируется следующим образом. Конечный автомат — это ориентированный граф, размеченный над полукольцом \mathcal{R}(V) регулярных языков в алфавите V с выделенной вершиной q_0, которая называется начальной, и с выделенным подмножеством вершин F, каждый элемент которого называется заключительной вершиной.


На функцию разметки при этом накладываются следующие ограничения: метка каждой дуги есть либо язык \{\lambda\}, либо непустое подмножество алфавита V.


Вершины графа называют обычно в этом случае состояниями конечного автомата, начальную вершину — начальным состоянием, а заключительную вершину — заключительным состоянием конечного автомата.


Замечание 7.5. Если для какой-то дуги e\in E ее метка \varphi(e) есть язык \{\lambda\}, то, поскольку этот язык не является подмножеством алфавита V, в этом случае \varphi(e)\nsubseteq V, и, наоборот, если \varphi(e)\subseteq V, то исключается, что \varphi(e)= \{\lambda\}. Таким образом, два рассмотренных случая для значений функции разметки исключают друг друга, на что и было указано в рассмотренном выше неформальном описании конечного автомата.


На рис. 7.5 изображен конечный автомат, для которого алфавит V=\{0;1\}. Начальное состояние показано входной стрелкой, заключительное — выходной. Метки дуг обычно пишут без фигурных скобок. Разрешена запись меток дуг и в виде регулярных выражений (см. рис. 7.5).


Конечный автомат, для которого алфавит V={0,1}

Конечный автомат, таким образом, может быть задан как пятерка:


M=(\mathcal{Q},E,\varphi,q_0,F),

где \mathcal{Q} — множество состояний автомата; E — множество дуг; \varphi — функция разметки (весовая функция), причем для каждой дуги e\in E ее метка \varphi(e)=\{\lambda\} или \varphi(e)\subseteq V, при этом подмножество \varphi(e) не пусто; q_0\in Q — начальное состояние; F\subseteq Q — подмножество заключительных состояний.


Алфавит V называется входным алфавитом автомата M, а его буквы — входными символами (или входными буквами) данного автомата.


Замечание 7.6. Конечный автомат определен как ориентированный граф, размеченный над полукольцом регулярных языков, но метка дуги задается не как произвольный регулярный язык, а как язык, состоящий из одной пустой цепочки, либо язык, являющийся подмножеством букв входного алфавита. Это ни в коей мере не противоречит основному определению размеченного ориентированного графа, ибо совершенно не обязательно, чтобы область значения функции разметки совпадала с носителем полукольца. Чисто формально, конечно, можно обобщить определение конечного автомата и допустить в качестве меток дуг произвольные регулярные языки, но, как можно показать, это обобщение не является принципиальным, и такое определение конечного автомата сводится к данному выше определению (см. задачи в конце этой главы). Немаловажно и то, что приведенное формальное определение конечного автомата и задание меток дуг как регулярных языков специального вида согласуются с интуитивным представлением об автомате как об устройстве, которое "побуквенно" читает входные цепочки, переходя из одного состояния в другое. Требование, чтобы такое устройство за один такт анализировало ("обозревало") любое, сколь угодно сложное регулярное выражение, не отвечает нашей "вычислительной" интуиции, в соответствии с которой за один такт может быть произведена только простая операция, каковой и является "реакция" автомата на обозреваемый одиночный символ или на пустую цепочку.




Если e=(q,r) — дуга автомата M и ее метка \varphi(e) есть регулярное выражение \lambda, то в этом случае будем говорить, что в автомате M возможен переход из состояния q в состояние r по пустой цепочке, и писать q\to_{\lambda}r. Дугу с меткой \lambda будем называть λ-переходом (или пустой дугой).


Если же метка дуги e есть множество, содержащее входной символ а, то будем говорить, что в автомате M возможен переход из состояния q в состояние r по символу a, и писать q\to_{a}r.


Для конечного автомата удобно ввести в рассмотрение функцию переходов, определив ее как отображение


\delta\colon\, Q\times (V\cup\{\lambda\})\to 2^Q такое, что \delta(q,a)=\{r\colon\, q\to_{a}r\},

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


На рис. 7.5 \delta(q_0,0)=\{q_0,q_1\},~ \delta(q_0,1)=\{q_0\},~ \delta(q_1,0)=\{q_2\},~ \delta(q_1,1)=\varnothing,~ \delta(q_2,0)=\{q_2\},~ \delta(q_2,1)=\{q_2\}.


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


Система команд есть конечное множество команд вида qa\to r, где q и r — состояния автомата; a — входной символ или пустая цепочка, причем указанная команда тогда и только тогда содержится в системе команд, когда q\to_{a}r.


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


Система команд автомата, изображенного на рис. 7.5, приведена ниже:


\begin{array}{lll}q_00\to q_0,&\qquad q_00\to q_1,&\qquad q_01\to q_0,\\ q_10\to q_2,&\qquad q_20\to q_2,&\qquad q_21\to q_2. \end{array}

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


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

где V — входной алфавит; Q — множество состояний; q_0 — начальное состояние; F — множество заключительных состояний; \delta — функция переходов, заданная в виде системы команд. Как правило, в дальнейшем мы именно так и будем определять конечный автомат.


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


(\forall q\in Q)(\forall a\in V)(\delta(q,a)\ne\varnothing).

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


Конечный автомат называется детерминированным, если в нем нет дуг с меткой \lambda и из любого состояния по любому входному символу возможен переход в точности в одно состояние, то есть


(\forall q\in Q)(\forall a\in V)(|\delta(q,a)|=1).

Конечный автомат называется квазидетерминированным, если в нем нет дуг с меткой \lambda и из любого состояния по любому символу возможен переход не более чем в одно состояние, т.е.


(\forall q\in Q)(\forall a\in V)(|\delta(q,a)|\leqslant1).

Замечание 7.7. Для детерминированного конечного автомата значением функции переходов для любой пары (состояние, входной символ) является одноэлементное подмножество множества состояний. Поэтому естественно понимать функцию переходов детерминированного конечного автомата не как отображение множества Q\times V в множество 2^Q, а как отображение множества Q\times V в само множество состояний Q. Впредь так и будем рассматривать функцию переходов детерминированного конечного автомата, не оговаривая этого особо.


Согласно общему определению метки пути в размеченном ориентированном графе, метка пути в конечном автомате есть соединение* меток входящих в этот путь дуг (в порядке их прохождения). Таким образом, метка любого пути конечной длины в конечном автомате есть регулярный язык. Отметим, что мы, изучая размеченные ориентированные графы, предполагаем, что рассматриваются только пути конечной длины. Так, для автомата, изображенного на рис. 7.5, метка пути q_0,q_0,q_1,q_2 равна соединению языков \{0;1\}\cdot\{0\}\cdot\{0\}= \{000;100\}, что можно записать в виде регулярного выражения (0+1)00, а метка пути q_0,q_1,q_2,q_2,q_2 может быть задана таким регулярным выражением:


00(0+1)(0+1)= 00(00+01+10+11)= 0000+0001+0010+0011,

что означает, что эта метка есть множество цепочек \{0000;0001;0010;0011\}.


*Умножением полукольца \mathcal{R}(V) является соединение языков.


Метку пути W конечной длины обозначим через \varphi^{\ast}(W). Здесь \varphi^{\ast} — это функция, отображающая множество всех путей конечной длины в размеченном ориентированном графе, в полукольцо \mathcal{R}(V). Для пути W длины 1 значение \varphi^{\ast}(W)=\varphi(W), т.е. функция разметки ориентированного графа есть ограничение функции \varphi^{\ast} на множество всех путей длины 1.


Если цепочка x принадлежит метке некоторого пути W — пути, ведущего из вершины q в вершину r конечного автомата M, то говорят, что цепочка x читается на пути W в M или что путь W несет цепочку x. Пишем q \Rightarrow_{x}^{\ast}r, если x читается на некотором пути из q в r. В том случае, когда явно надо указать длину n пути, на котором читается цепочка x, записываем q \Rightarrow_{x}^{n}r. Если нужно подчеркнуть, что цепочка x читается на некотором пути ненулевой длины из q в r, то используем запись q \Rightarrow_{x}^{+}r. В терминах неформального описания конечного автомата любому пути, на котором читается входная цепочка x, отвечает последовательность конфигураций, которую проходит автомат, читая посимвольно входную цепочку, записанную на ленте, и продвигая головку на один символ вправо за один такт.


Стоимость прохождения из состояния q в состояние r есть (согласно общему определению этого понятия в размеченных ориентированных графах) объединение меток всех путей*, ведущих из q в r, т.е. множество всех таких x, что q\Rightarrow_{x}^{\ast}r. Это значит, что элемент c_{qr} матрицы стоимостей есть язык


c_{qr}=\{x\colon\, q\Rightarrow_{x}^{\ast}r\}.

*Здесь объединение понимается как бесконечная сумма замкнутого полукольца \mathcal{L}(V) всех языков в алфавите V, т.е. как точная верхняя грань последовательности языков относительно теоретико-множественного включения.


Говоря об элементе c_{qr} матрицы стоимостей, мы отождествляем обозначение состояния автомата с его номером в некоторой нумерации состояний как вершин ориентированного графа.


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


L(M)=\{x\colon\, q_0\Rightarrow_{x}^{\ast}q_f,~ q_f\in F\}= \bigcup\limits_{q_f\in F}c_{q_0q_f}\,,
(7.5)

где F — множество заключительных состояний.


Таким образом, язык конечного автомата есть объединение тех элементов матрицы стоимостей автомата, которые находятся в строке, соответствующей начальному состоянию q_0, и в столбцах, соответствующих всем заключительным состояниям q_f\in F.


Замечание 7.8. Необходимо обратить внимание на одну очень важную вещь. В конечном автомате метка произвольного пути конечной длины есть регулярный язык, поскольку он вычисляется как соединение конечного семейства регулярных языков. Но стоимость прохождения между заданной парой вершин априори не является регулярным языком, так как множество путей, ведущих из одной вершины в другую, может быть бесконечным (каждый путь имеет конечную длину, но множество всех таких путей может оказаться бесконечным, содержать пути сколь угодно большой длины — простейший пример дает петля, по которой можно пройти сколько угодно раз). Поэтому объединение при определении стоимости прохождения между парой состояний конечного автомата мы можем сейчас рассматривать только как операцию замкнутого полукольца всех языков в данном алфавите, а именно операцию вычисления точной верхней грани ("бесконечная сумма" в замкнутом полукольце). Но коль скоро элементы матрицы стоимостей уже вычислены, их объединение (в формуле (7.5)), дающее язык конечного автомата, разумеется, конечно. Позже будет доказано, что на самом деле все стоимости в конечном автомате также регулярны.

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

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


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

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