Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 15

Начальное состояние, одно из состояний в Д. 5. Множество заключительных, или допускающих, состояний г. Множество Р'является подмножеством Д. В дальнейшем детерминированный конечный автомат часто обозначается как ДКА. Наиболее компактное представление ДКА — это список пяти вышеуказанных его компонентов. В доказательствах ДКА часто трактуется как пятерка А = (О, Х, б, г)о, Г), где А — имя ДКА, Д вЂ” множество состояний, Х вЂ” множество входных символов, б— функция переходов, г),— начальное состояние и Р— множество допускающих состояний. 2.2.2, Как ДКД обрабатывает цепочки Первое, что следует выяснить о ДКА, — это понять, каким образом ДКА решает, "допускать" ли последовательность входных символов.

"Язык" ДКА — это множество всех его допустимых цепочек. Пусть а~аз...а„— последовательность входных символов. ДКА начинает работу в начальном состоянии ~ус. Для того чтобы найти состояние, в которое А перейдет после обработки первого символа аи мы обращаемся к функции переходов б. Пусть, например, 4<)е, а~) = ггь Для следующего входного символа аз находим 4дь аз), Пусть это будет состояние дз. Аналогично находятся и последующие состояния фь 44 .", г)„, где адьо а,) = ~у, для каждого й Если д„принадлежит множеству Р; то вход- '1'очнее говоря, граф есть изображение некоторой функции переходов б, а дуги этого графа отображают переходы, определяемые функцией а ГЛАВА 2.

КОНЖЧНЪ(Е АВТОМАТЫ 62 ная последовательность а,аэ...а„допускается, в противном случае она "отвергается" как недопустимая. Пример 2.1. Определим формально ДКА, допускающий цепочки из 0 и 1, которые содержат в себе подцепочку 01. Этот язык можно описать следующим образом: !ж ! ж имеет вид хО!у, где х ну — цепочки, состоящие только из 0 и 1). Можно дать и другое, эквивалентное описание, содержащее х и у слева от вертикальной черты: (хО !у ~ х ну — некоторые пеночки, состоящие иэ 0 и 1).

Примерами цепочек этого языка являются цепочки 01, 110!0 и 1000111. В качестве примеров цепочек, не принадлежащих данному языку, можно взять цепочки е, 0 и 111000. Что мы знаем об автомате, допускающем цепочки данного языка?? Во-первых, что алфавитом его входных символов является Х = !О, 1). Во-вторых, имеется некоторое множество Д состояний этого автомата. Один из элементов этого множества, скажем, ао, является его начальным состоянием, Для того чтобы решить, содержит ли входная последовательность подцепочку 01, автомат А должен помнить следующие важные факты относительно прочитанных им входных данных. 1.

Была ли прочитана последовательность О!? Если это так, то всякая читаемая далее последовательность допустима, т.е. с этого момента автомат будет находиться лишь в допускающих состояниях. 2. Если последовательность 01 еще не считана, то был ли на предыдущем шаге считан символ О? Если это так, и на данном шаге читается символ 1, то последовательность 01 будет прочитана, и с этого момента автомат будет находиться только в допус- кающнх состояниях. 3.

Действительно ли последовательность 01 еще не прочитана, и на предыдущем шаге на вход либо ничего не подавалось (состояние начальное), либо был считан символ 1? В этом случае А не перейдет в допускающее состояние до тех пор, пока им не будут считаны символы 0 и сразу за ним 1. Каждое из этих условий можно представить как некоторое состояние.

Условию (3) соответствует начальное состояние о!о. Конечно, находясь в самом начале процесса, нужно последовательно прочитать 0 и 1. Но если в состоянии о?о читается 1, то это нисколько не приближает к ситуации, когда прочитана последовательность 01, поэтому нужно оставаться в состоянии о!о. Таким образом, Ждо, 1) = г?о. Однако если в состоянии ао читается О, то мы попадаем в условие (2), т.е. 01 еще не прочитаны, но уже прочитан О.

Пусть д, обозначает ситуацию, описываемую условием (2). Переход из ?о по символу 0 имеет вид б(ао, 0) = аэ Рассмотрим теперь переходы из состояния аь При чтении 0 мы попадаем в ситуацию, которая не лучше предыдущей, но и не хуже. 01 еще не прочитаны, но уже прочитан О, и 2.2. ДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 63 теперь ожидается 1. Эта ситуация описывается состоянием ~уж поэтому определим б(дь 0) = оз. Если же в состоянии дз читается 1, то становится ясно, что во входной последовательности непосредственно за 0 следует !.

Таким образом, можно перейти в допускающее состояние, которое обозначается о1 и соответствует приведенному выше условию (1), т.е. фдь 1) = дь Наконец, нужно построить переходы в состоянии оь В этом состоянии уже прочитана последовательность 01, и, независимо от дальнейших событий, мы будем находиться в этом же состоянии, т.е. асуп 0) = Жу~ ! ) = Чь Таким образом, Д = (ом дь оз). Ранее упоминалось, что оя — начальное, а гу~ — единственное допускающее состояние автомата, т.е.

Р = (о~). Итак, полное описание автомата А, допускающего язык ь' цепочек, содержащих 01 в качестве подцепочки, имеет вид А = ((Оо <?ь с7г) (О, 1), б Чо (В)). где д — функция, описанная выше. П 2.2.3. Более простые представления ДКА Определение ДКД как пятерки обьектов с детальным описанием функции переходов слишком сухое и неудобочитаемое. Существует два более удобных способа описания ав- томатов.

1. Диаграчма переходов, которая представляет собой граф (его пример приведен в разделе 2.1). 2. Таблица переходов, дающая табличное представление функции б. Из нее очевидны состояния и входной алфавит. Диаграммы переходов Диаграмма переходов для ДКА вида А = (Д, Е, 6, зм Р) есть граф, определяемый следующим образом: а) всякому состоянию из Д соответствует некоторая вершина; б) пусть ф), а) =)з для некоторого состояния о из Д и входного символа а из Х. Тогда диаграмма переходов должна содержать дугу из вершины о в вершину р, отмеченную а. Если существует несколько входных символов, переводя- щих автомат из состояния о в состояние р, то диаграмма переходов может содержать одну лугу, отмеченную списком этих символов; в) диаграмма содержит стрелку в начальное состояние, отмеченную как Начало.

Эта стрелка не выходит ни из какого состояния; г) вершины, соответствующие допускающим состояниям (состояниям из Р)„ отмечаются двойным кружком. Состояния, не принадлежащие г", изображаются простым (одинарным) кружком. ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ Пример 2.2. На рис. 2.4 изображена диаграмма переходов для ДКА, построенного в примере 2.! На диаграмме видны три вершины, соответствующие трем состояниям, стрелка Начато, ведущая в начальное состояние е!а, и одно допускающее состояние с!ь отмеченное двойным кружком, Из каждого состояния выходят две дуги: одна отмечена О, вторая — 1 (для состояния |!| дуги объединены в одну).

Каждая дуга соответствует одному из фактов для б, построенных в примере 2.1, ьл 1 О Начало О цо 0,1 Рис. 2.4, Диаграл|л|а переходов для ДКА, допускаю|чего все цепочки, которые содержат подцепочку О! Таблицы переходов Таблица переходов представляет собой обычное табличное представление функции, подобной б, которая двум аргументам ставит в соответствие одно значение. Строки таблицы соответствуют состояниям, а столбцы — входным символам. На пересечении строки, соответствующей состоянию |2, и столбца, соответствующего входному символу а, находится состояние 6(|1, а).

Пример 2.3. На рис. 2.5 представлена таблица переходов, соответствующая функции б из примера 2.1. Кроме того, здесь показаны и другие особенности таблицы переходов. Начальное состояние отмечено стрелкой, а допускающее — звездочкой. Поскольку прописные символы строк и столбцов задают множества состояний и символов, у нас есть вся информация, необходимая лля однозначного описания данного конечного автомата. 14 Рис. 2.5. Таблица переходов дляДКА из примера 2.! 2.2.4. Расширение функции переходов на цепочки Ранее было нестрого обосновано утверждение о том, что всякий ДКА определяет некоторый язык, а именно; множество всех цепочек, приводящих автомат из начального состояния в одно из допускающих.

В терминах диаграмм переходов язык ДКА— это множество меток вдоль всех путей, ведущих из начального состояния в любое до- пускающее. 2.2. ДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ Теперь дадим строгое определение языка ДКА. С этой целью определим расширенную функцию нереходое, которая описывает ситуацию, при которой мы, начиная с про- извольного состояния, отслеживаем произвольную последовательность входных символов. Если Ю вЂ” наша функция переходов, то расширенную функцию, построенную по 4 обозначим 6. Расширенная функция переходов ставит в соответствие состоянию с) и цепочке зг состояние р, в которое автомат попадает из состояния д, обработав входную последовательность зг.