dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 14
Текст из файла (страница 14)
Еще один пример:существует дуга с меткой R, ведущая из состояния (4, c) в (4, e), поскольку выкуп переводит банк из состояния 4 снова в состояние 4, а магазин — из c в e.60Стр. 60ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ2.1.5. Ïðîâåðêà ïðîòîêîëà ñ ïîìîùüþ àâòîìàòà-ïðîèçâåäåíèÿИз рис. 2.3 можно узнать кое-что интересное. Так, из начального состояния (1, a) —комбинации начальных состояний банка и магазина — можно попасть только в десять извсех 28 состояний. Заметим, что такие состояния, как (2, e) и (4, d), не являются достижимыми, т.е. пути, ведущего к ним из начального состояния, не существует.
Нет надобности включать в автомат недостижимые состояния, и в нашем случае это сделано исключительно для последовательности изложения.Однако реальной целью анализа протоколов, подобных данному, с помощью автоматов является ответ на вопрос: “возможна ли ошибка данного типа?”. Простейший пример: нас может интересовать, возможно ли, что магазин доставит товар, а оплаты за неготак и не получит, т.е. может ли автомат-произведение попасть в состояние, в котороммагазин уже завершил доставку (и находится в одном из состояний в столбцах c, e илиg), и при этом перехода, соответствующего входу T, никогда ранее не было и не будет.К примеру, в состоянии (3, e) товар уже доставлен, но переход в состояние (4, g), соответствующий входу T, в конце концов произойдет. В терминах действий банка это означает, что если банк попал в состояние 3, то он уже получил запрос на выкуп и обработал его.
Значит, он находился в состоянии 1 перед получением этого запроса, не получалтребования об отмене и будет игнорировать его в будущем. Таким образом, в концеконцов банк переведет деньги магазину.Однако в случае состояния (2, e) мы сталкиваемся с проблемой. Состояние достижимо, но единственная выходящая дуга ведет в него же. Это состояние соответствует ситуации, когда банк получил сообщение об отмене раньше, чем запрос на выкуп.
Но магазин получил сообщение об оплате, т.е. наш пройдоха-клиент одни и те же деньги и потратил, и отменил. Магазин же, по глупости, доставил товар прежде, чем попыталсявыкупить деньги. Теперь, если магазин выполнит запрос на выкуп, то банк даже не подтвердит получение соответствующего сообщения, так как после отмены, находясь в состоянии 2, банк не будет обрабатывать запрос на выкуп.2.2. Äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòûТеперь пора ввести формальное понятие конечного автомата и уточнить рассужденияи описания из разделов 1.1.1 и 2.1. Начнем с рассмотрения формализма детерминированного конечного автомата, который, прочитав любую последовательность входныхданных, может находиться только в одном состоянии.
Термин “детерминированный” говорит о том, что для всякой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. В противоположность детерминированному, “недетерминированный” конечный автомат, который рассматривается в разделе 2.3, может находиться сразу в нескольких состояниях. Под термином“конечный автомат” далее подразумевается автомат детерминированного типа. Но2.2. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр.
6161обычно для того, чтобы напомнить читателю, автомат какого типа рассматривается,употребляется слово “детерминированный” или сокращение ДКА (DFA — DeterministicFinite Automaton).2.2.1. Îïðåäåëåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòàДетерминированный конечный автомат состоит из следующих компонентов.1.Конечное множество состояний, обозначаемое обычно как Q.2.Конечное множество входных символов, обозначаемое обычно как Σ.3.Функция переходов, аргументами которой являются текущее состояние и входнойсимвол, а значением — новое состояние.
Функция переходов обычно обозначаетсякак δ. Представляя нестрого автомат в виде графа, мы изображали δ отмеченнымидугами, соединяющими состояния. Если q — состояние и a — входной символ, тоδ(q, a) — это состояние p, для которого существует дуга, отмеченная символом a иведущая из q в p.24.Начальное состояние, одно из состояний в Q.5.Множество заключительных, или допускающих, состояний F. Множество F являетсяподмножеством Q.В дальнейшем детерминированный конечный автомат часто обозначается как ДКА.Наиболее компактное представление ДКА — это список пяти вышеуказанных его компонентов. В доказательствах ДКА часто трактуется как пятеркаA = (Q, Σ, δ, q0, F),где A — имя ДКА, Q — множество состояний, Σ — множество входных символов, δ —функция переходов, q0 — начальное состояние и F — множество допускающих состояний.2.2.2.
Êàê ÄÊÀ îáðàáàòûâàåò öåïî÷êèПервое, что следует выяснить о ДКА, — это понять, каким образом ДКА решает,“допускать” ли последовательность входных символов. “Язык” ДКА — это множествовсех его допустимых цепочек. Пусть a1a2…an — последовательность входных символов.ДКА начинает работу в начальном состоянии q0. Для того чтобы найти состояние, в которое A перейдет после обработки первого символа a1, мы обращаемся к функции переходов δ. Пусть, например, δ(q0, a1) = q1. Для следующего входного символа a2 находимδ(q1, a2). Пусть это будет состояние q2.
Аналогично находятся и последующие состоянияq3, q4, …, qn, где δ(qi-1, ai) = qi для каждого i. Если qn принадлежит множеству F, то входТочнее говоря, граф есть изображение некоторой функции переходов δ, а дуги этого графаотображают переходы, определяемые функцией δ.262Стр. 62ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛная последовательность a1a2…an допускается, в противном случае она “отвергается” какнедопустимая.Пример 2.1. Определим формально ДКА, допускающий цепочки из 0 и 1, которыесодержат в себе подцепочку 01. Этот язык можно описать следующим образом:{w | w имеет вид x01y, где x и y — цепочки, состоящие только из 0 и 1}.Можно дать и другое, эквивалентное описание, содержащее x и y слева от вертикальной черты:{x01y | x и y — некоторые цепочки, состоящие из 0 и 1}.Примерами цепочек этого языка являются цепочки 01, 11010 и 1000111.
В качестве примеров цепочек, не принадлежащих данному языку, можно взять цепочки ε ,0 и 111000.Что мы знаем об автомате, допускающем цепочки данного языка L? Во-первых, чтоалфавитом его входных символов является Σ = {0, 1}. Во-вторых, имеется некотороемножество Q состояний этого автомата. Один из элементов этого множества, скажем, q0,является его начальным состоянием. Для того чтобы решить, содержит ли входная последовательность подцепочку 01, автомат A должен помнить следующие важные фактыотносительно прочитанных им входных данных.1.Была ли прочитана последовательность 01? Если это так, то всякая читаемая далеепоследовательность допустима, т.е.
с этого момента автомат будет находиться лишьв допускающих состояниях.2.Если последовательность 01 еще не считана, то был ли на предыдущем шаге считансимвол 0? Если это так, и на данном шаге читается символ 1, то последовательность01 будет прочитана, и с этого момента автомат будет находиться только в допускающих состояниях.3.Действительно ли последовательность 01 еще не прочитана, и на предыдущем шагена вход либо ничего не подавалось (состояние начальное), либо был считан символ1? В этом случае A не перейдет в допускающее состояние до тех пор, пока им не будут считаны символы 0 и сразу за ним 1.Каждое из этих условий можно представить как некоторое состояние. Условию (3)соответствует начальное состояние q0. Конечно, находясь в самом начале процесса, нужно последовательно прочитать 0 и 1.
Но если в состоянии q0 читается 1, то это нискольконе приближает к ситуации, когда прочитана последовательность 01, поэтому нужно оставаться в состоянии q0. Таким образом, δ(q0, 1) = q0.Однако если в состоянии q0 читается 0, то мы попадаем в условие (2), т.е. 01 еще непрочитаны, но уже прочитан 0. Пусть q2 обозначает ситуацию, описываемую условием(2).
Переход из q0 по символу 0 имеет вид δ (q0, 0) = q2.Рассмотрим теперь переходы из состояния q2. При чтении 0 мы попадаем в ситуацию,которая не лучше предыдущей, но и не хуже. 01 еще не прочитаны, но уже прочитан 0, и2.2. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 6363теперь ожидается 1. Эта ситуация описывается состоянием q2, поэтому определимδ(q2, 0) = q2. Если же в состоянии q2 читается 1, то становится ясно, что во входной последовательности непосредственно за 0 следует 1. Таким образом, можно перейти в допускающее состояние, которое обозначается q1 и соответствует приведенному выше условию (1), т.е.
δ(q2, 1) = q1.Наконец, нужно построить переходы в состоянии q1. В этом состоянии уже прочитанапоследовательность 01, и, независимо от дальнейших событий, мы будем находиться вэтом же состоянии, т.е. δ(q1, 0) = δ(q1, 1) = q1.Таким образом, Q = {q0, q1, q2}. Ранее упоминалось, что q0 — начальное, а q1 — единственное допускающее состояние автомата, т.е. F = {q1}. Итак, полное описание автомата A, допускающего язык L цепочек, содержащих 01 в качестве подцепочки, имеет видA = ({q0, q1, q2}, {0, 1}, δ, q0, {q1}),где δ — функция, описанная выше. 2.2.3.
Áîëåå ïðîñòûå ïðåäñòàâëåíèÿ ÄÊÀОпределение ДКА как пятерки объектов с детальным описанием функции переходовслишком сухое и неудобочитаемое. Существует два более удобных способа описания автоматов.1.Диаграмма переходов, которая представляет собой граф (его пример приведен в разделе 2.1).2.Таблица переходов, дающая табличное представление функции δ. Из нее очевиднысостояния и входной алфавит.Äèàãðàììû ïåðåõîäîâДиаграмма переходов для ДКА вида A = (Q, Σ, δ, q0, F) есть граф, определяемый следующим образом:а) всякому состоянию из Q соответствует некоторая вершина;б) пусть δ(q, a) = p для некоторого состояния q из Q и входного символа a из Σ.Тогда диаграмма переходов должна содержать дугу из вершины q в вершинуp, отмеченную a.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
