3645 ТЕОРИЯ АВТОМАТОВ В ЗАДАЧАХ

1.Введение в теорию конечных автоматов

1.1. Основные понятия и определения

На протяжении последних десятилетий велись и ведутся интенсивные работы по созданию и использованию различных систем и устройств для переработки дискретной информации. Преобразователи дискретной информации широко применяются в качестве различного рода технических автоматов, вычислительных устройств и их функциональных блоков, устройств управления роботами, управляющих объектами по заданному алгоритму и т.д. Широкий класс таких преобразователей объединяется под общим названием автомат. При одном из подходов к определению термина автомат его истолковывают как математическую модель реальных преобразователей дискретной информации. Функционирование его состоит в том, что последовательность z1, z2… символов конечного или в общем случае бесконечного алфавита Z, поступающая на вход, вызывает на его выходе определенную последовательность ω1, ω2, … символов того же или другого алфавита. Таким образом, самой общей математической моделью преобразователя дискретной информации (ПДИ) является последовательностная функция φ: Z*→W*, отображающая множество Z* всех последовательностей символов алфавита Z в другое множество W* последовательностей символов алфавита W (рис. 1.1).

 

 

 

 

 

Рис.1.1. Общая функциональная                    Рис.1.2. Формальная……… модель ПДИ                                                          модель ПДИ
Такая интерпретация позволяет схематично представить преобразователь как устройство, реализующее отображение одного множества на другое (рис. 1.2).

Отображение φ называется алфавитным (автоматным) отображением или алфавитным оператором. Результат преобразования вход => выход (рис. 1.2) зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, от предыстории преобразования. Чтобы как-то запоминать предыстории и отличать одну от другой, преобразователь должен иметь память. Для этого в модель (рис. 1.2) вводят алфавит состояний Q={q1, q2,…,qm} и такой преобразователь (рис. 1.3) называют конечным автоматом (КА), если множество входных сигналов Z и множество возможных состояний Q конечны. Преимущество конечности числа состояний заключается в том, что устройство можно реализовать, имея ограниченные ресурсы, либо аппаратно (в “железе”), либо в виде простой программы, принимающей решение на основе ограниченного количества данных или текущей команды машинного кода. Таким образом, конечные автоматы включают набор состояний и переходов между ними, зависящих от входных данных.

 

 

 

Рис.1.3. Конечный автомат             Рис.1.4. КА, моделирующий
переключатель

Конечный автомат – это устройство, работающее в дискретные моменты времени (такты). На вход его в каждом такте поступает один из возможных сигналов, а на выходе вырабатывается выходной сигнал, являющийся функцией его текущего состояния (q) и поступившего входного сигнала (z), то есть ω=λ(q,z). Внутреннее состояние автомата также меняется, и новое состояние q=(t+1) является функцией δ тех же двух аргументов: q(t+1)= δ(q,z).

Понятие текущего состояния q играет важную роль в работе КА,  так как определяет его будущее поведение – реакцию на последующие входные сигналы.

Простейшим нетривиальным конечным автоматом является переключатель «включено-выключено». Это устройство помнит свое состояние, и от этого состояния зависит результат нажатия кнопки. Из состояния «выключено»  нажатие кнопки переводит переключатель в состояние «включено», и наоборот.

Конечно-автоматная модель переключателя представлена на рис.1.4

Как и для всех конечных автоматов, состояния обозначены кружками, а переходы между ними – дугами. Дуги отмечаются «входными символами», задающими внешние воздействия на систему (устройство). В примере это Нажатие, что означает нажатие на кнопку переключателя. Стрелки указывают, что всякий раз при Нажатии система переходит из одного состояния в другое. Одно из состояний является так называемым «начальным состоянием» (в нашем случае – «выкл.»), в котором система находится изначально. На рисунке оно отмечено словом Начало и стрелкой, указывающей на это состояние.

Часто необходимо выделять одно или несколько «заключительных» или «допускающих» состояний. Если в результате реализации некоторой последовательности входных воздействий автомат попадает в одно из них, то такую последовательность можно считать в определенном смысле «хорошей». Например, состояние «вкл.» (рис.1.4) можно рассматривать как допускающее, поскольку если переключатель находится в этом состоянии, то устройство, управляемое им, находится в рабочем режиме. Этот признак будет использован далее при рассмотрении КА- распознавателей, определяющих принадлежность заданной входной последовательности (цепочки) заданному языку (см. п.1.5).

Различают две основных модели конечных автоматов – автоматы Мили и Мура. Автоматы Мура отличаются тем, что выходной сигнал является функцией только текущего состояния, т.е. ω=λ(q). Модель КА (рис.1.3), имеющую один вход и один выход, называют еще абстрактным автоматом (АА), поскольку в ней абстрагируются от реальных физических входных и выходных сигналов, рассматривая их просто как буквы некоторого алфавита и в связи с идеализированным дискретным временем.

Преобразователи дискретной информации, математической моделью которых является АА, называют цифровыми автоматами (ЦА). Автоматы с числом внутренних состояний более одного | Q | >1 составляют класс автоматов с памятью. Далее, если не оговорено противное, будем рассматривать автоматы общего вида – автоматы Мили. Частным случаем таких автоматов является устройство, в котором значение выходного символа ωq не зависит от состояния и определяется текущим входным символом zf.  Все состояния в нем эквивалентны, и можно считать, что такой автомат имеет одно состояние и по сути понятие состояния оказывается лишним. Функция переходов δ в нем вырождена. Поведение его однозначно задается функцией выходов.

Математической моделью устройства является функция ω(t)=λ(z(t)). Такие автоматы называются автоматами без памяти или комбинационными схемами (КС).

1.2. Формальное описание КА

С математической точки зрения конечный автомат – это шестерка объектов:

А=(Z, W, Q, δ, λ, q 0  ),

где Z= {z1, z2, …,zn} – множество входных символов (входной алфавит);

W= {w1, w2,…,wG} – множество выходных символов (выходной алфавит);

Q= {q1, q2,…,qR} – множество состояний автомата (алфавит состояний);

δ: Q×Z→Q – функция переходов;

λ: Q×Z→Z – функция выходов;

q0ÎQ – начальное состояние автомата.

Задание начального состояния q(t=0) = q0 имеет принципиальное значение, ибо, не зная его, невозможно определить реакцию автомата на любое входное слово. Функции переходов и выходов зависят от двух аргументов, поэтому, не зная q0, нельзя найти q(1), q(2), …, а также w(1), w(2),…. Автомат с выделенным начальным состоянием (обычно это q0) называется инициальным.

Функционирование КА описывается системой:

 

,                                       (1)

 

т.е. указываются закон изменения состояния к следующему тактовому моменту (t+1) в зависимости от входного символа z(t) и предыстории q(t), а также значение выходного символа wq (t) в текущий тактовый момент как функции λ состояния q(t) и входного символа z(t) в тот же момент времени. Автомат, для которого функции δ и λ определены на всех парах (qm ,zf), называют полностью определенным или полным, а тот, для которого  функция δ или λ или обе функции определены не на всех парах, – не полностью определенным или частичным.

КС на абстрактном уровне описывается тройкой объектов:

A=(Z, W, λ),

где  Z и W – входной и выходной алфавиты соответственно, а

λ - функция выходов.

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

Реализация КА приведена на рис. 1.5.

 

 

 

 

 

 

 

Рис. 1.5. Реализация КА

 

Логический блок ЛБ вырабатывает выходные сигналы W и сигналы U, позволяющие изменить текущее состояние автомата. Блок памяти БП автомата хранит информацию о текущем состоянии Q, которое вместе с входным сигналом Z определяет выходную реакцию автомата W и следующее состояние.

 

1.3. КА – модель цифровых автоматов

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

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

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

-       проектирование систем технической диагностики;

-       проектирование узлов и блоков ЭВМ и других вычислительных систем и устройств;

-       проектирование устройств промышленной автоматики и др.

Однако интерпретация автомата как устройства является важной, но не универсальной, поскольку отражает лишь один из аспектов его работы – преобразование множества входных слов Z* в множество выходных W*, т.е. реализацию автоматного отображения оператора. Такой подход является источником многих задач, рассматриваемых при проектировании автоматов-преобразователей.

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

1.4. КА-распознаватели

При рассмотрении автоматов с алгоритмической точки зрения возможности автоматов изучают в терминах множеств слов, с которыми они работают, интересуются тем, какие множества конечных последовательностей входных сигналов Z* можно отличить друг от друга с помощью выходных сигналов, иначе – принадлежит ли поданное на вход слово заданному множеству, т.е. языку.

С точки зрения теории алгоритмов КА можно рассматривать как некоторый алгоритм, принимающий в качестве входа символ за символом произвольную цепочку w над словарем Z (словарем будем называть конечное множество элементов, элементы словаря – символами, последовательности символов словаря – цепочками или предложениями, а их множество – языком. Язык над словарем Z будем обозначать как LZ или просто L). Выходом его будет один из двух возможных ответов: «да», т.е. wÎL, либо «нет», т.е. wÏL .

Любой конечный механизм задания языка L называется грамматикой. Существуют два типа грамматик – порождающие и распознающие.

Под первой понимается конечный набор правил, позволяющий строить все правильные предложения языка L. Распознающая грамматика задает критерий принадлежности произвольной цепочки w данному языку.

Таким образом, КА можно рассматривать как устройство, выполняющее алгоритмические операции над языками. Простейшей из них является распознавание – выделение автоматом всех входных предложений, принадлежащих языку.

Метод распознавания использует частичный алгоритм, который для произвольной входной цепочки x остановится и ответит «да» после конечного числа шагов, если эта цепочка принадлежит языку. Такой алгоритм определяет язык L как множество входных цепочек, для которых он выдает «да».

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

Таким образом, распознаватель – это схематизированный алгоритм, распознающий принадлежность объекта заданному классу.                            Иначе – алгоритм  отвечает на вопрос: «Истинно ли высказывание хÎM?» и выдает ответ «да» или «нет». Такими распознавателями являются конечные автоматы (КА), автоматы с магазинной памятью (АМП), машины Тьюринга (МТ) и др.

Вспомогательная память может быть в виде потенциально бесконечной ленты, как в МТ, либо магазинного типа, как в АМП, либо вообще отсутствовать, как в КА.

 

 

 

 

 

 

 

 

Рис. 1.6. Общий вид распознавателя

1.5. Формальное описание КА-распознавателя

С математической точки зрения КА-распознаватель – это пятерка объектов:

А=(Q, Z, q0, δ, F ),

где Q – конечное непустое множество состояний (алфавит состояний);

Z–входной алфавит (конечное множество допустимых входных сигналов);

q0ÎQ – начальное состояние;

δ:QxZ®Q – функция переходов;

FÍQ – множество заключительных (допускающих) состояний.

Он может быть задан таблицей переходов, в которой на пересечении строки, соответствующей символу zj, и столбца, соответствующего состоянию qi, ставится новое состояние q1=d(zj,qi), либо графом, вершины которого отмечены состояниями, а дуги соответствуют переходам (qi,qi1), если существует такой символ zÎZ, что

q1=d (q,z) в случае детерминированного КА и

q1Îd (q,z) – в случае недетерминированного.

Начальное состояние q0 отмечается направленной в него стрелкой со словом «начало», а заключительное – двойным кружком. КА может быть описан и аналитически как процесс порождаемых автоматом А конфигураций для заданной входной цепочки aÎZ.

«Работа» КА представляет собой некоторую последовательность шагов (тактов), каждый из которых определяется текущим состоянием qi и входным символом zj, обозреваемым СГ в данный момент времени. Сам шаг есть считывание символа, изменение состояния КА и сдвиг СГ на одну ячейку вправо. Чтобы определить будущее поведение КА, надо знать лишь текущее состояние qi и цепочку символов a на входной ленте, состоящую из символа под СГ и всех символов, расположенных вправо от нее. Эти два элемента информации d(q, a)ÎQxZ дают мгновенное описание КА и называются конфигурацией автомата А.

Конфигурация (q0, a) называется начальной, а пара (q,e), где qÎF, – заключительной (или допускающей) конфигурацией. Такт автомата А представляется бинарным отношением ├А, определенным на конфигурациях. Если d(q, a) содержит q¢, то (q, za) ├А (q¢,a) для всех aÎZ. Это говорит о том, что если автомат А находится в состоянии q и СГ обозревает входной символ z, то он может делать такт, за который переходит в состояние q¢ и сдвигает СГ.

Различают детерминированные (ДКА) и недетерминированные конечные автоматы (НКА). Термин «детерминированный» говорит о том, что для всякой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. «Язык» ДКА – это множество всех допустимых им цепочек. Вопрос о «допуске» последовательности входных символов ДКА решают следующим образом. Говорят, что КА–распознаватель А=(Q, Z, q0, δ, F) допускает цепочку, если (q0,α)├A* (q, e) для некоторого qÎF, т.е. если α переводит его из начального в одно из заключительных состояний δ*(q0, α)ÎF. Множество всех цепочек, допускаемых автоматом А, образуют язык, допускаемый A.

Очевидно LA={αÎZ*|δ*(q0,α)ÎF }.

В противоположность  детерминированному «недетерминированный» КА обладает свойством находиться сразу в нескольких состояниях одновременно. Эту особенность часто представляют как свойство автомата делать «догадки» относительно его входных данных. Всякий такой автомат допускает язык, допустимый некоторым ДКА, т.е. НКА допускает регулярные языки точно так же, как и ДКА. Различие между ними состоит в типе значений функции δ. В НКА ее значение – некоторое подмножество множества Q, т.е. для НКА – это множество состояний, а для ДКА – одиночное состояние. Будем считать, что НКА допускает цепочку ω, если в процессе чтения ее символов можно выбрать хотя бы одну последовательность переходов в следующие состояния так, чтобы прийти из начального состояния в одно из допускающих. Формально, если А=(Q, Z, q0, δ, F) – некоторый НКА, то LA={w|δ*(q0, w)Ç F=Æ}. Таким образом, L(А) есть множество цепочек w из Z*, для которых среди состояний δ*(q0,w) есть хотя бы одно допускающее.

Пример. Построить НКА, допускающий только те цепочки из 0 и 1, которые оканчиваются на 01.

Для решения вопроса о допустимости заданной цепочки рассмотрим ситуации, которые должен помнить автомат относительно прочитанных входных символов Z={0,1}.

Начальным является состояние q0, в котором автомат будет находиться ( а также, возможно, и в других состояниях) до тех пор, пока не «догадается», что на входе началась замыкающая подцепочка 01.

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

 

 

 

 

 

 

 

Рис. 1.7. Граф НКА, допускающего цепочки, оканчивающиеся на 01

 

Вместе с тем если очередной входной символ – 0, то НКА может предположить, что уже началась замыкающая последовательность 01, поэтому дуга с меткой 0 ведет из состояния q0 в q1 . Заметим, что из q0 выходят две дуги, отмеченные символом 0, т.е. автомат может перейти как в q0, так и в q1 и в действительности переходит в оба эти состояния. В состоянии q1 автомат проверяет, является ли следующий входной символ единицей. Если да, то он переходит в состояние q2 и считает эту цепочку допустимой.

Заметим, что ДКА в каждом состоянии имеет ровно одну выходящую дугу для каждого входного символа, а для НКА такого ограничения нет.


Далее рассмотрим, как такой НКА обрабатывает цепочку w=00101(рис.1.8).

Таблица 1.1

 

Рис. 1.8. Процесс обработки цепочки w

 

Прочитав последовательность 001, НКА находится в состояниях q0 и q2 и допускает последовательность, поскольку q2 - допускающее состояние. Однако чтение входных символов не закончено. Четвертый входной символ 0 приводит к тому, что ветвь, соответствующая q2, отмирает (нет выхода по 0), в то время как q0 переходит в q0 и q1. По последнему символу происходит переход из q0 в q0, а из q1 - в q2. Поскольку автомат вновь переходит в допускающее состояние q2, цепочка w=00101 допустима, т.е. wÎLA. Такой НКА (рис. 1.7)   можно задать формально как А=({q0, q1, q2},{0,1},d,q0,{q2}), где функция переходов задается табл. 1.1.