Глава 5 конечные автоматы в задачах обработки текстов

Содержание

Конечный автомат: теория и реализация

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

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

Примечание автора Хоть в статье используются ActionScript 3 и Flash, вы с легкостью можете писать на удобном для вас языке.

Что такое конечный автомат?

Конечный автомат (или попросту FSM — Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Описание состояний автомата

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра — переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

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

Описание состояний интеллекта муравья

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

21–22 ноября, Минск, 229–349 $

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

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

Описание состояний интеллекта муравья. Обратите внимание на отсутствие перехода между «run away» и «go home»

Реализация простого конечного автомата

Конечный автомат можно реализовать при помощи одного класса. Назовем его FSM. Идея состоит в том, чтобы реализовать каждое состояние как метод или функцию. Также будем использовать свойство activeState для определения активного состояния.

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

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

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM — это делает наш класс более универсальным.

Использование конечного автомата

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

Описание состояний интеллекта муравья, сосредоточенное на коде

Наш муравей представлен классом Ant, в котором есть поле brain. Это как раз экземпляр класса FSM.

Класс Ant также содержит свойства velocity и position. Эти переменные будут использоваться для расчета движения с помощью метода Эйлера. Функция update() вызывается при каждом обновлении кадра игры.

Для понимания кода мы опустим реализацию метода moveBasedOnVelocity(). Если хотите узнать поподробнее на тему движения, прочитайте серию статей Understanding Steering Behaviors.

Ниже приводится реализация каждого из методов, начиная с findLeaf() — состояния, ответственного за поиск листьев.

Состояние goHome() — используется для того, чтобы муравей отправился домой.

И, наконец, состояние runAway() — используется при уворачивании от курсора мыши.

Улучшение FSM: автомат, основанный на стеке

Представьте себе, что муравью на пути домой также нужно убегать от курсора мыши. Вот так будут выглядеть состояния FSM:

Обновленное описание состояний интеллекта муравья

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

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

Конечный автомат, основанный на стеке

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Переходы в FSM, основанном на стеке

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

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

Вывод

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

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

Конечные автоматы. Автоматизированный практикум

Детерменированный конечный автомат. Минимизация конечных автоматов. Вопросы кодирования и представления, обработки и минимизации конечного автомата. Разработка программы на языке C#, которая демонстрирует все алгоритмы обработки конечных автоматов.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 17.05.2015
Размер файла 578,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФГБОУ ВПО КубГТУ)

Кафедра Информационных систем и программирования

Институт Компьютерных систем и информационной безопасности

По дисциплине Теория конечных автоматов и формальных языков

На тему Конечные автоматы. Автоматизированный практикум

Выполнил студент группы 12-КБ-ПР1

Марков Владислав Сергеевич

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФГБОУ ВПО КубГТУ)

Кафедра Информационных систем и программирования

Институт Компьютерных систем и информационной безопасности

Зав. Кафедрой ИСП

«____» _______________2014 г.

на курсовую работу

Студенту Маркову Владиславу Сергеевичу группы 12- КБ- ПР1 3 курса института компьютерных систем и информационной безопасности

направления 231000 — Программная инженерия

Тема работы: Конечные автоматы. Автоматизированный практикум

Содержание задания: Изучить тему «Конечные автоматы», разработать программу, демонстрирующую работы конечного автомата, разработать различные алгоритмы обработки конечных автоматов

Объём курсовой работы:

а) пояснительная записка 20 стр. .

Рекомендуемая литература Ключко, Власенко, Кушнир «Теория

автоматов и формальных языков . Учебное пособие».

Срок выполнения работы: с 3 сентября 2014г. по 20 декабря 2014г.

Дата защиты: 10 ноября 2014г.

Дата выдачи задания: 3 сентября 2014 г.

Дата сдачи работы на кафедру: 1 ноября 2014г. по 20 декабря 2014г.

Руководитель работы __________________________________________

Задание принял студент ________________________________________

Стр. 20, рис. 10, библ. 3.

КОНЕЧНЫЙ АВТОМАТ, ЭКВИВАЛЕНТНЫЕ СОСТОЯНИЯ,

НЕДОСТИЖИМЫЕ СОСТОЯНИЯ, КОДИРОВАНИЕ, ПЕРЕХОДНЫЕ

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

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

1. Конечный автомат

1.1 Детерменированный конечный автомат

1.2 Недетерменированный конечный автомат

1.3 Минимизация конечных автоматов

2. Алгоритм расчёта

3. Руководство пользователя

Список используемых источников

Введение

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

1. Конечный автомат

Программисты очень часто сталкиваются с проблемой разделения строк на некоторые осмысленные части, проверки правильности ввода значений и т.д. В принципе, так как очень часто пользователем является человек, то самым естественным для него путем передачи информации будет человеческая речь. Тем не менее, задача выделения смысла из человеческой речи до сих пор не решена, поэтому для подобных случаев используется формальные описания некоторых структур — формальные грамматики. Конечные автоматы применяются для простейших грамматик. Обычно КА применятся для того, что называется лексическим анализом, т.е. для разбиения исходной строки на набор некоторых лексических единиц (например, выделение из текста слов и чисел). Простейший детерминированый КА работает следующим образом: в нем находится внутренний регистр для хранения текущего состояния и таблица правил вида «символ-состояние => состояние» позволяющая по текущему символу на ленте и текущему состоянию перейти в другое состояние (со сдвигом по ленте). Цепочка символов допустима, если КА завершил свою работу в одном из «разрешенных» состояний и не допустима в обратном случае.

1.1 Детерменированный конечный автомат

1) S — множество состояний управляющего устройства

2) L — входной алфавит (каждая клетка входной ленты содержит символ из I),

3) a — отображение SxL в S (если a( s ,a1 ) = s`, то всякий раз, когда М находится в состоянии s , а входная головка обозревает символ a1 , М сдвигает входную головку вправо и переходит в состояние s`),

4) s- выделенное состояние в S, называемое начальным

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

Пример ДКА изображен на рис 1

Рис.1 Пример ДКА

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

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

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

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

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

Таблица переходов — табличное представление функции F. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ. Пример таблицы переходов изображен на рисунке 2

Рис. 2 Таблица переходов

1.2 Недетерменированный конечный автомат

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

Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали и такие атоматы называются эквивалентными. Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

Рис.3. Пример НКА с пустыми переходами

Недетерминированным конечным автоматом называется множество (S, L, a , s, F), где

1) S — конечное множество состояний устройства управления;

2) L — алфавит входных символов;

3) a- функция переходов, отображающая S x (I U ) в множество подмножеств множества S;

4) s — начальное состояние устройства управления;

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

Рис.4 НКА из одного состояния выходит несколько переходов, помеченных одним символом

С каждым НКА связан ориентированный граф, естественным образом представляющий функцию переходов этого автомата.

Приведем определение для графа ( или диаграммы) переходов автомата М = (S, I, a, s , F). Графом переходов автомата М называют ориентированный граф G = (S, E) с помеченными ребрами.

Существует дополнительный результат или возможность сопоставить какому-либо взятому НКА эквивалентную «детерминированную» машину. Однако детерминированный конечный автомат, эквивалентный данному НКА с n состояниями, может иметь вплоть до 2 в n степени состояний. Поэтому переход от НКА к детерминированному автомату не всегда дает эффективный способ моделирования недетерминированного конечного автомата.

1.3 Минимизация конечных автоматов

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

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

Автоматы упрощаются/минимизируются:

1. Удалив недостижимые состояния;

2. Удалив непродуктивные состояния;

3. Выявив эквивалентные состояния.

Для описания процесса нахождения наименьшего КА введем следующие определения:

Состояние qQ называется недостижимым, если под воздействием любого слова xУ* автомат не переходит в состояние q. То есть не существует слово x, для которого есть переход в состояние q.

В КА на рисунке 5 состояние q3 — недостижимое.

Рис. 5 Пример автомата с недостежимым состоянием

Непродуктивным называется то состояние qQ для которого не существует xУ* для которого (q0, x)(q, x1)(qf,) (нет вывода до финального состояния).

В КА на рисунке 6 состояние q3 — непродуктивное.

Рис. 6 Автомат с непродуктивным состоянием

Известно уже что два автомата называются эквивалентными, если они распознают один и тот же язык над алфавитом .

Учитывая, что можно определять эквивалентные автоматы, хотелось бы научиться находить наименьший среди них.

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

Говорят, что слово x различает состояния q1, q2 (q1, q2Q), если одно из этих состояний финальное, а другое не является заключительным.

Состояния q1 и q2 конечного автомата называются различными (неэквивалентны), если существует слово (цепочка) x, которое различает эти два состояния (из одного состояния достижимо заключительное состояние, а из другого — нет).

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

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

Описание алгоритма минимизации конечного автомата:

1. Находим и удаляем в начальном КА все недостижимые и непродуктивные состояния.

2. Затем необходимо найти такое разбиение множества всех оставшиехся состояний автомата, чтобы каждое подмножество содержало неразличимые состояния. То есть множества состояний автомата разделяются на классы эквивалентности:

a) В I-й класс относим все конечные/финальные состояния (то есть состояния из множества F);

b) Во II-й класс относим все остальные состояния (то есть Q\F).

Назовем эти состояния 0-эквивалентными.

3. Строим новое одно-эквивалентное разбиение, выделив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния.

4. Повторяется шаг 3, последовательно создавая (n+1)-эквивалентные состояния по n-эквивалентным, увеличивая так число классов эквивалентности.

5. Алгоритм заканчивается, когда (n+1)-эквивалентные состояния совпадают с n-эквивалентными.

Каждый полученный класс эквивалентности будет новым состоянием в новом минимизированном автомате.

В множество F’ автомата внесём те состояния, которые содержат хотя бы одно финальное состояние из начального.

Полученный, минимизированный КА должен быть эквивалентен начальному КА.

2. Алгоритм расчёта

Для формирования конечного автомата на вход подаётся конфигурационный файл вида:

N — количество состояний;

Матрица переходов состояний;

Матрица переходов выходных сигналов.

2.2 Описание алгоритма

конечный автомат программа алгоритм

Для кодирования конечного автомата применён следующий алгоритм:

1. Программа получает данные из файла, записывая их в численные матрицы переходов.

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

3. Для нахождения потенциально эквивалентных состояний мы обрабатывали матрица переходов, где искали пары состояний с одинаковым выходных сигналом, заносили их в список.

4. Для нахождения недостижимых состояний обрабатывали матрицу переходов состояний, где искали состояний, в которые конечный автомат никогда не переходит, заносили их в список.

3. Руководство пользователя

Запуск программы сопровождается открытием окна:

Рисунок 7 — Загрузка КА

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

Рисунок 8 — Кодирование КА

Следующая вкладка представляет возможным найти все потенциально эквивалентные состояния.

Рисунок 9 — Нахождение ПЭС

И в последней вкладке пользователь может найти все недостижимые состояния.

Рисунок 10 — Недостижимые состояния.

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

Данная работа позволила нам более подробно рассмотреть такой объект, как конечный автомат. Основным моментом проведённого исследования является создания автоматизированного комплекса в виде приложения, которые позволяет наглядно продемонстрировать все возможности конечных автоматов.

Список используемых источников

1. Ключко В.И., Власенко А.В., Кушнир Н.В. Теория автоматов и формальных языков: учеб. пособие/Кубан. гос. технол. ун-т.- Краснодар: Изд. ФГБОУ ВПО «КубГТУ», 2012.- 151 с.

2. Теория автоматов и формальных языков. Методические указания к курсовому проекту для студентов всех форм обучения направлений 23100062 — Программная инженерия, 23070062 — Прикладная информатика / Сост.: А.В.Власенко, В.И.Ключко, Н.В.Кушнир; Кубан. гос. технол. ун-т. Каф. вычислительной техники и АСУ. — Краснодар: Изд. КубГТУ, 2012. — 23 с.

3. Теория автоматов и формальных языков: метод. указания по выполнению лабораторных работ для студентов всех форм обучения по направлениям 231000.62 Программная инженерия, 230700.62 Прикладная информатика / Сост.: В.И. Ключко, А.В. Власенко, Н.В. Кушнир; Кубан. гос. технол. ун-т. Каф. вычислительной техники и АСУ. — Краснодар.: Изд. ФГБОУ ВПО «КубГТУ», 2012. — 44 с.

Дискретная математика в примерах и задачах, Тишин В.В., 2008

Дискретная математика в примерах и задачах, Тишин В.В., 2008.

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

Распознавание множеств автоматами.
Изобразить недетерминированный источник, соответствующий недетерминированному автомату, заданному таблицей переходов, с входным алфавитом (а,b) и множеством внутренних состояний (1,2,3,4,5). При построении использовать возможно меньшее число дуг. В построенном недетерминированном источнике желательно присутствие хотя бы одного пустого ребра. Если построить соответствующий недетерминированный источник с пустым ребром невозможно, докажите это.

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

Если недетерминированный источник содержит пустую дугу, выходящую из i-той вершины и заходящую в k-ю вершину, то, очевидно, должны выполняться два условия:
1) i-тая вершина не встречается в какой-либо клетке таблицы автомата без k-той вершины;
2) множество вершин, в которое можно попасть, считав любой символ входного алфавита, из вершины k, включено во множество вершин, в которое можно попасть из вершины i, считав тот же символ.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава 1. Множества, графики, соответствия, отношения.
1.1. Операции над множествами.
1.2. Графики.
1.3. Соответствия.
1.4. Отношения.
Глава 2. Булевы функции.
2.1. Булевы функции. Суперпозиции.
2.2. Булевы функции и теория множеств.
2.3. Нормальные формы и полиномы.
2.4. Классы Поста.
2.5. Минимизация нормальных форм всюду определённых булевых функций.
2.6. Частичные функции и схемы.
Глава 3. Теория алгоритмов.
3.1 Машины Тьюринга.
3.2. Нормальные алгоритмы.
3.3. Рекурсивные функции.
Глава 4. Предикаты.
4.1. Предикаты.
Глава 5. Комбинаторика.
5.1. Сочетания, размещения, перестановки.
5.2. Бином Ньютона и полиномиальная формула.
5.3. Формула включений и исключений.
5.4. Задачи о распределениях.
5.5. Арифметический треугольник.
5.6. Рекуррентные соотношения.
Глава 6. Конечные автоматы.
6.1. Автоматы Мили.
6.2. Частичные автоматы.
6.3. Реализация автоматов схемами.
6.4. Распознавание множеств автоматами.
Список литературы.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Дискретная математика в примерах и задачах, Тишин В.В., 2008 — fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России. Купить эту книгу

3645 теория автоматов в задачах

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Рязанская государственная радиотехническая академия

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

Методические указания к практическим занятиям

УДК 519. 713 (075)

Теория автоматов в задачах . Ч1: Методические указания к практическим занятиям/ Рязан. гос. радиотехн. акад. Сост.: Н.И. Иопа. Рязань, 2004. 36 с.

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

Предназначены для студентов специальности 2201 «Вычислительные машины, комплексы, системы и сети» дневного и вечернего отделений, могут быть полезными студентам специальности 0752 «Компьютерная безопасность» и других специальностей.

Табл. 23. Ил. 37. Библиогр.: 5 назв.

Преобразователи, автоматы, модели, автоматные операторы, автоматные модели, распознаватели, конечные автоматы, машины Тьюринга, абстрактный синтез

Печатается по решению методического совета Рязанской государственной радиотехнической академии.

Рецензент: кафедра ЭВМ РГРТА (зав. кафедрой проф. В.К. Злобин)

Теория автоматов в задачах

Составитель И о п а Николай Иванович

Редактор Р.К. Мангутова

Корректор Е.В. Ипатова

Подписано в печать 10.09.04. Формат бумаги 60х84 1/16.

Бумага офсетная. Печать трафаретная. Усл.печ. л.2,25.

Уч.-изд. л. 2,25. Тираж 50 экз. Заказ

Рязанская государственная радиотехническая академия.

390005, Рязань, ул. Гагарина, 59/1.

Редакционно-издательский центр РГРТА.

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= и такой преобразователь (рис. 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 не зависит от состояния и определяется текущим входным символом z f . Все состояния в нем эквивалентны, и можно считать, что такой автомат имеет одно состояние и по сути понятие состояния оказывается лишним. Функция переходов δ в нем вырождена. Поведение его однозначно задается функцией выходов.

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

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

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

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

W= – множество выходных символов (выходной алфавит);

Q= – множество состояний автомата (алфавит состояний);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Он может быть задан таблицей переходов , в которой на пересечении строки, соответствующей символу z j , и столбца, соответствующего состоянию q i , ставится новое состояние q 1 =(z j ,q i ), либо графом, вершины которого отмечены состояниями, а дуги соответствуют переходам (q i ,q i 1 ), если существует такой символ zZ, что

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

q 1  (q,z) – в случае недетерминированного.

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

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

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

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

В противоположность детерминированному « недетерминированный » КА обладает свойством находиться сразу в нескольких состояниях одновременно. Эту особенность часто представляют как свойство автомата делать «догадки» относительно его входных данных. Всякий такой автомат допускает язык, допустимый некоторым ДКА, т.е. НКА допускает регулярные языки точно так же, как и ДКА. Различие между ними состоит в типе значений функции δ. В НКА ее значение – некоторое подмножество множества Q, т.е. для НКА – это множество состояний, а для ДКА – одиночное состояние. Будем считать, что НКА допускает цепочку ω, если в процессе чтения ее символов можно выбрать хотя бы одну последовательность переходов в следующие состояния так, чтобы прийти из начального состояния в одно из допускающих. Формально, если А=(Q, Z, q 0 , δ, F) – некоторый НКА, то L A =<|δ*(q 0 , ) F=>. Таким образом, L(А) есть множество цепочек  из Z*, для которых среди состояний δ*(q 0 ,) есть хотя бы одно допускающее.

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

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

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

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

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

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

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

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

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

Прочитав последовательность 001, НКА находится в состояниях q 0 и q 2 и допускает последовательность, поскольку q 2 — допускающее состояние. Однако чтение входных символов не закончено. Четвертый входной символ 0 приводит к тому, что ветвь, соответствующая q 2 , отмирает (нет выхода по 0), в то время как q 0 переходит в q 0 и q 1. По последнему символу происходит переход из q 0 в q 0 , а из q 1 — в q 2. Поскольку автомат вновь переходит в допускающее состояние q 2, цепочка =00101 допустима, т.е. L A . Такой НКА (рис. 1.7) можно задать формально как А=(,<0,1>,,q 0 ,), где функция переходов задается табл. 1.1.

1.6. Примеры КА-распознавателей

Пример 1. Построить детерминированный КА, допускающий в алфавите Z= <0,1>все цепочки нулей и единиц, содержащие подцепочку 00, например =01001. Язык L A =. Тогда =1101101 L А .

Чтобы построить автомат, необходимо задать все компоненты вектора А=(Z, Q, q 0 , δ, F). Изначально известно лишь, что алфавитом входных символов является Z= <0,1>и что имеется множество состояний этого автомата. Чтобы решить, содержит ли входная последовательность подцепочку 00, автомат А должен помнить следующие факты относительно прочитанных им входных данных.

1. Два нуля («00») еще не появились. На выходе либо ничего не подавалось (начальное состояние), либо на предыдущем шаге символ не был нулем.

2. Два нуля («00») не появились, но предыдущий символ был нулем.

3. Два нуля («00») появились, и тогда всякая считанная далее последовательность допустима, т.е. с этого момента автомат будет находиться лишь в допускающих состояниях.

Каждое из этих условий можно представить как некоторое состояние. Условию 1 соответствует начальное состояние q 0 . Конечно, находясь в начале процесса, нужно последовательно прочитать 0 и 1. Но если в состоянии q 0 читается 1, то это не приближает нас к ситуации, когда прочитана последовательность «00», поэтому нужно оставаться в состоянии q 0 , т.е. q 0, 1) = q 0 . Однако если в состоянии q 0 читается 0, то мы попадаем в условие 2, т.е. два нуля еще не прочитаны, но уже прочитан «0», и обозначим эту ситуацию через q 1 , q 1 =q 0, 0).

Если в состоянии q 1 читается 0, понятно, что во входной последовательности идет второй 0 подряд, и можно перейти в допускающее состояние (q 2 ), которому соответствует условие 3. В случае если в q 1 читается 1, то необходимо вернуться в начальное состояние q 0 , т.к. ясно, что двух нулей подряд не получится. Следовательно, q 1, 0) = q 2, q 1, 1) = q 0 .

Таким образом, Q=, где q 0 – начальное состояние, а q 2 – единственное допускающее состояние автомата, т.е. F=. Полное описание автомата, допускающего язык L (цепочек, содержащих «00» в качестве подцепочки), имеет вид: А=(,<0,1>,,q 0 ,), где  задается табл. 1.2.

Рис. 1.9. ДКА, допускающий

Далее проверим, допускает ли построенный ДКА цепочку =01001. В п. 1.5 отмечалось, что ДКА допускает цепочку , если (q 0 ,)F, т.е. если последний символ цепочки переводит автомат в заключительное состояние.

Процесс порождения конфигураций для заданной цепочки будет следующим:

(q 0 , 01001)├ (q 1 , 1001) ├ (q 0 , 001) ├ (q 1 ,01) ├ (q 2 , 1) ├ (q 2 ,е).

П оскольку ├ А * ( ), то ω=01001L(A).

Пример 2. Построить НКА, допускающий цепочки в алфавите Z=, у которых последний символ цепочки уже появлялся в ней раньше, например ω=z1z2z3z2z1.

Определим компоненты вектора А= и в частности множество Q=, где:

q 0 – начальное состояние автомата, в котором автомат не пытается ничего распознать, он или какой-то его экземпляр находится в так называемом нейтральном состоянии;

q 1 , q 2 , q 3 – состояния, в которых автомат делает предположение о том, что последний символ цепочки совпадает с индексом состояния;

q 4 F — заключительное состояние.

Формально автомат описывается пятеркой А=(,, δ, q 0, ), где δ задается табл. 1.3. Граф автомата представлен на рис.1.10

Рис. 1.10. Граф автомата

Далее проверим принадлежность языку L(А) цепочек  1 =z2z1z1z3z2; 2=z3z1z1z3z2. Процессы порождения конфигураций для  1 и 2 приведены на рис.1.11 и 1.12 соответственно.

Рис.1.11.Порождение конфигураций для  1

Т ак как ├ * (q 4 ,e), то .

Рис. 1.12. Порождение конфигураций для 2

Поскольку под действием последнего символа цепочки  2 автомат не переходит в заключительное состояние,  2  L ( S ).

1.7. Задачи

1. Построить ДКА, допускающий в алфавите Z <0,1>все цепочки нулей и единиц, содержащие в себе:

а) подцепочки 01, например 01, 11010, 1000111;

б) подцепочку 11;

в) подцепочку 100;

г) множество цепочек, которые начинаются или оканчиваются (или и то и другое) последовательностью 01;

д) множество всех цепочек, в которых всякая подцепочка из пяти последовательных символов содержит хотя бы два 0.

2. Определить, допускает ли автомат, заданный графом (рис. 1.13), цепочки  1 =z1 z2 z2 z3 z1 z3;  2 =z2 z1 z3 z3 z1 z2;  3 =z2 z3;  4 =z1 z3, если q 0 F.

3. Построить КА, допускающий все цепочки, в которых за каждой единицей непосредственно следует «0».

4. Построить КА с входным алфавитом V=, распознающий:

а) все цепочки, в которых две последние буквы не совпадают;

б) все цепочки, начинающиеся и заканчивающиеся различными символами;

в) все цепочки, у которых последний символ цепочки уже появлялся раньше.

5. Построить ДКА, допускающий в алфавите Z <0,1>все цепочки, содержащие четное число 0 и четное число 1.

6. Преобразовать НКА (рис.1.7) в ДКА.

7 . Построить НКА:

а) с входным алфавитом V=,распознающий множества цепочек: abc, abd, aacd;

б) с входным алфавитом V=,распознающий множества цепочек: ab, bc, ca;

в) с входным алфавитом Z=<0,1>, распознающий множества цепочек: 1010, 101, 011.

Рис. 1.13. Граф автомата

1.8. КА-преобразователи


1.8.1. Классификация автоматов

По виду деятельности, весьма разнообразной, автоматы можно сгруппировать в три основных класса:

Примерами информационных автоматов являются справочные автоматы на вокзалах, светофоры, устройства аварийной сигнализации; управляющих – кодовый замок, устройства управления лифтом, шлагбаумом железнодорожного переезда, различными типами станков ; вычислительных – процессор ЭВМ, АЛУ, спецпроцессоры либо простое вычислительное устройство, выполняющее одну или несколько арифметических и логических операций, таких как AA+B+C (сложение с переносом), AA-C (вычитание заема), AAB (конъюнкция А и В). В сложных системах-автоматах, таких как ЭВМ, пульт управления энергосистемой и др., выполняются все три указанных вида деятельности.

1.8.2. Абстрактный синтез автоматов

Абстрактной модели КА соответствует этап абстрактного синтеза, который заключается в переходе от первоначальной записи условий работы проектируемого ЦА к стандартному заданию его автоматного оператора. К стандартным формам относятся в том числе и таблицы переходов-выходов, и графы. В свою очередь этап абстрактного синтеза включает два подэтапа:

На первом получают таблицы переходов-выходов автомата, который может содержать лишние внутренние состояния, что отражается на объеме устройства. Функция состояний заключается в том, чтобы участвовать в определении зависимости между входами и выходами автомата, и физической природой состояний при этом не интересуются. Следовательно, любое множество состояний, выполняющих эту функцию, является приемлемым, независимо от того, выражают они какой-либо интуитивный смысл или нет. Эта свобода выбора множества состояний весьма выгодна, поскольку позволяет заменить одно множество другим и, в частности, найти оптимальное или минимальное множество состояний. В основе минимизации множества состояний лежит понятие эквивалентности и гомоморфизма автоматов.

При использовании конечно-автоматной модели в реальных задачах элементам формальной системы придаются конкретные свойства и признаки .

1.8.3. Примеры КА–преобразователей и их синтез

Пример 1. Построить КА, управляющий шлагбаумом (ш/б) железнодорожного (ж/д) переезда.

1. Первоначальное описание условий работы ЦА

Схема движения поездов и автотранспорта через железнодорожный переезд, регулируемый шлагбаумом, приведена на рис.1.14.

Рис. 1.14. Регулируемый железнодорожный переезд

Для разработки алгоритма работы ЦА рассмотрим ситуации.

Если первая колесная пара ведущего вагона поезда миновала пункт А на ж/д полотне, то ш/б будет закрыт.

Если последняя колесная пара последнего вагона прошла пункт В при движении поезда слева, то ш/б будет открыт.

Если первая колесная пара ведущего вагона поезда при движении справа миновала пункт С на ж/д полотне, то ш/б будет закрыт.

Если последняя колесная пара последнего вагона прошла пункт D при движении поезда справа, ш/б будет закрыт.

Условие 2 должно быть выполнено, если нет поезда справа или он еще не достиг пункта С.

Условие 4 должно быть выполнено, если нет поезда слева или он еще не достиг пункта А.

2. Стандартное описание автоматного оператора ЦА

Для формального описания модели проектируемого ЦА необходимо задать все компоненты вектора S=. Будем считать, что символы А, В, С, Д – идентификаторы сигналов о пересечении поездами соответствующих пунктов ж/д полотна и являются символами входного алфавита Z, т.е. Z=. На основе анализа ситуаций работы автомата введем понятие «опасной зоны» (заштрихована), которая свидетельствует о том, что переезд закрыт, если хотя бы один из поездов пересек пункт А или С. Такая условность позволяет сократить число возможных ситуаций, каждая из которых будет отмечена состоянием: q 0 – нет ни одного поезда в ОЗ; q 1 – наличие одного из поездов в ОЗ; q 2 – два поезда в ОЗ. Таким образом, Q=. Автомат должен формировать два выходных символа  0 – открыть ш/б;  1 – закрыть ш/б, т.е. W=< 0,  1 >. Формально автомат описывается шестеркой S=(, , < 0,  1 >, δ, , q 0 ), где функции δ и  задаются совмещенной таблицей переходов и выходов (табл.1.4). Граф, описывающий работу автомата, приведен на рис. 1.15.

Рис.1.15. Модель устройства, управляющего ш/б ж/д переезда

Пример 2. Построить конечно-автоматную модель 2-разрядного двоичного реверсивного счетчика (рис. 1.16) , способного работать как в режиме сложения, так и в режиме вычитания. Для формального описания работы КА необходимо задать все компоненты вектора А=, придав им конкретные свойства и признаки.

Рис. 1.16. Общий вид РС

Анализ условий работы РС

Число состояний автомата равно четырем и определяется самим заданием: РС содержит два элемента памяти – триггеры Т1,Т2, состояния которых Q1, Q2 и будут определять состояния автомата в целом Q=(см.табл. 1.5).

Для определения алфавитов Z и W проанализируем работу РС при различных комбинациях единичных входных импульсов.

При поступлении единичных импульсов на суммирующий вход X1 РС работает как суммирующий двоичный счетчик с модулем М=4, изменяя при этом свои состояния последовательно от q 0 до q 3 . Если в состоянии q 3 на автомат поступает очередной импульс по каналу X 1 , то счетчик обнуляется (состояние q 0 ) и начинает считать заново, а на выходе по каналу Y 1 выдается сигнал переполнения  1 , что соответствует комбинации на выходах: у 1 =1, у 2 =0. При этом комбинация на входных каналах (х 1 =1, х 2 =0) может повторяться сколь угодно долго. Однако при смене состояний внутри каждого цикла, т.е. q 0  q 1 , q 1  q 2 , q 2  q 3 , на выходе автомата будет формироваться другой абстрактный сигнал —  2, соответствующий комбинации (y 1 =0, y 2 =0).

При поступлении единичных импульсов на вычитающий вход x 2 РС работает как вычитающий двоичный счетчик с модулем М=4. Из состояния q 0 он переходит в состояние q 3 , а затем последовательно из q 3 в q 0 (рис. 1.17). При смене состояния с q 0 на q 3 на выходе формируется сигнал заема ( 3 ), что соответствует комбинации y 1 =0, y 2 =1. При смене состояний внутри цикла вычитания q 3  q 2 , q 2  q 1 , q 1  q 0 на выходе автомата формируется абстрактный сигнал  2 .Таким образом, входной алфавит Z=, W=< 1,  2,  3, >, где каждому абстрактному символу соответствуют комбинации сигналов на входе и выходе РС, приведенные в табл. 1.6, 1.7.

Таблица 1.6 Таблица 1.7

Очевидно, что комбинации (х1=1, х2=1) и (Y1=1, Y2=1) не имеют смысла, т.к. противоречат логике работы автомата.

Стандартное описание автоматного оператора РС

Ф ормально оператор описывается шестеркой А=(,, < 1,  2,  3, >, δ, ,q 0, ), где функции δ и  задаются совмещенной таблицей переходов и выходов (табл. 1.8). Граф работы КА приведен на рис. 1.17.

Рис. 1.17. Граф работы РС

Пример 3. Построить КА, вставляющий «0» в двоичную последовательность после четырех единиц подряд.

Анализ условий работы автомата

Входной алфавит Z= <0,1>определен здесь заданием. W=, где w 0 –вставить «0», w 1 – ничего не менять, повторить входной символ.

Содержательную сторону состояний определим следующим образом:

q 0 – ожидание двоичного символа;

q 1 – получена первая единица;

q 2 – получена вторая подряд единица;

q 3 – получена третья подряд единица;

q 4 – получена четвертая подряд единица.

При определении терминальных значений состояний q 1… q 4 существенным и определяющим является слово « подряд ». Если каждому из этих состояний присвоить значение «получена вторая, третья, четвертая единицы», то это будет уже другой КА, вставляющий «0» не после 4-х подряд идущих «1», а после каждых 4-х последовательно поступивших «1» в двоичной последовательности, например:

=0101101 0 11011 0 1…

Стандартное описание автоматного оператора ЦА

Формально заданный автомат описывается шестеркой А=(,<0,1>,, δ, , q 0 ), где δ и  задаются табл. 1.9. Граф работы КА приведен на рис. 1.18.

Рис.1.18. Граф автомата Мили, вставляющего «0» после 4-х подряд «1»

1.8.4. Задачи

Построить конечный автомат, выбрасывающий лишние пробелы в тексте.

Построить КА, добавляющий бит нечетности к цепочке из «0» и «1».

Построить модель кодового замка с пятью кнопками (А, Б, В, Г, Д), открывающегося при наборе кода В*Д и остающегося открытым, пока нажата кнопка Д. Символ *Z означает, что ни одна кнопка не нажата, символы А, Б, В, Г, ДZ соответствуют нажатой кнопке. Множество W=, где w 0 – замок открыт, w 1 – замок закрыт.

Построить КА, убирающий подчеркнутые нули в потоке битов:

и распознающий начальный и заключительный флажки.

Построить КА, продающий пиво и выдающий сдачу. Автомат может принимать монеты достоинством 5 и 10 рублей, а кружка пива стоит 15 рублей. Кроме отверстий для приема монет и выдачи сдачи у автомата есть кнопки «Наливай» и «Сброс».

Построить КА для продажи билетов на пригородный поезд. Автомат может принимать монеты достоинством 5 копеек, 10 копеек, 50 копеек, 1 рубль. Цена билета 2 рубля 15 копеек. Таким образом, Z=<5 к., 10 50 1 р., *>, где * — отсутствуют монеты. W=<0, 1, С>, где 1 – дать билет, 0 – не давать билет, С – сброс. Сигнал «1» может быть выдан только при точном наборе стоимости билета.

Построить конечно-автоматную модель вычитающего двоичного счетчика последовательного счета с модулем М=5, обладающего свойством самовосстановления после сбоя (в качестве элементов памяти использовать ТС-триггеры).

Построить конечно-автоматную модель суммирующего двоичного счетчика последовательного счета с модулем М=5, обладающего свойством самовосстановления после сбоя (в качестве элементов памяти использовать ТС-триггеры).

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

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

Построить КА, управляющий движением лифта 6-этажного жилого дома, отличающийся от КА (задача 10) возможностью «подбирать» пассажиров, попутно следующих а) вниз; б) вверх, т.е. входной сигнал принимается не только стоящим, но и движущимся лифтом.

Построить КА, вставляющий дополнительный нуль в двоичную последовательность после каждых пяти подряд идущих единиц. Например, двоичную последовательность 001111110010011111110 автомат должен преобразовать в последовательность 0011111 0 10010011111 0 110 (подчеркнуты автоматически вставленные биты).

Построить КА, управляющий светофором автоматического регулирования транспорта на перекрестке (рис.1.19). Каждый из светофоров может показывать один из сигналов: К, Ж, З, стрелка, мигающий зеленый, мигающий желтый (ночной). Управление светофорами должно быть согласовано так, чтобы не создавалась аварийная ситуация.

Рис. 1.19. Регулируемый перекресток

Построить конечный автомат, управляющий движением транспорта на перекрестке главной и второстепенной улиц. Для каждой из них показывается один из сигналов: К, Ж, З и мигающий зеленый. Естественно, что автомат должен управлять светофором так, чтобы не создавалась аварийная ситуация (например, не должно быть зеленого сигнала на главной и второстепенной улицах одновременно). С 23 часов до 6 часов утра светофор переводится в режим мигания.

Построить КА, обеспечивающий пешеходам возможность пересечь магистраль, движение по которой регулируется автоматическим 3-секционным светофором (К, Ж, З). Движение транспорта по магистрали должно прекращаться по требованию пешехода нажатием кнопки. Разрешение пешеходу должно быть и визуальным, и звуковым. Возврат автомата в режим авторегулирования должен быть автоматическим.

1.8.5. Автоматы, реализующие набор арифметико-логических операций

1. Общие сведения и структура операционного автомата

Академик В.М. Глушков показал, что любое устройство обработки цифровой информации можно представить в виде совокупности двух взаимодействующих автоматов (рис. 1.20) – управляющего УА и операционного ОА.

Рис. 1.20. Структура ЦА

ОА осуществляет непосредственную обработку данных путем выполнения элементарных операций над словами (передача, сдвиг, хранение и др.) и выдает результат преобразования в виде двух слов: А — результат и F — признаки результата («флажки»), т.е. осведомительные сигналы о знаках и особых значениях промежуточных и конечных результатов операций, таких, например, как равенство нулю результата операции, знак результата и др. Выполнение элементарных операций инициируется соответствующими управляющими сигналами, которые формируются УА. По каждому сигналу y i выполняется одно из элементарных действий (сдвиг, обнуление регистра и др.). Их последовательность определяется сигналами Z кода операции КОП, поступающими на УА извне, и осведомительными сигналами . Операционный и управляющий автоматы отличаются не только по назначению, но и по объему памяти. Если в ОА он практически бесконечен, то в УА – сравнительно небольшой (до 100 тысяч бит).

На этапе структурного синтеза ОА представляют в виде двух частей – памяти и комбинационной схемы КС (рис. 1.21). КС служит для преобразования входных сигналов Х и информации о состоянии устройства (А) в выходные сигналы Y и сигналы возбуждения элементов памяти U.

Рис. 1.21. Обобщенная структура ОА

Поведение структуры (рис. 1.21) описывается четырьмя группами различных сигналов:X – входное слово, Y=(X,A) – выходное слово, U=Ψ(X,A) – слово (функция), обеспечивающее порядок смены состояний автомата, и А – слово, характеризующее состояние автомата. Внутреннее состояние автомата А определяется состоянием триггеров a r  <0,1>и описывается словом состояния А=( a 1, a 2, . a r , … a R ), . Множество слов |A| определяет объем памяти ОА. Объем памяти рассматриваемых в пособии ОА ограничен 16 битами. Рассматриваются 4-разрядные ОА, формирующие слово-состояние А= a 3 a 2 a 1 a 0 .

Задача синтеза ОА сводится:

— к выбору типа элементов памяти (триггеров), который может быть задан и заранее;

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

— к реализации системы ПФ (2) на заданной элементной базе (дискретные ИС, ПЛИС и др.).

В случае если автомат оказывается сложным, задачу синтеза ОА упрощают, декомпозируя (разделяя) его на более простые автоматы ОА1 и ОА2 (рис. 1.22) с одинаковой структурой (рис. 1.23).

Рис. 1.22. Декомпозиция ОА

Арифметико-логический автомат ОА1 формирует слово А результата операции и сигналы f S , f C , f Z , f P , f C ’ – логические функции признаков (ЛФП), относящиеся к выходным сигналам Y=λ(X,A), на основе которых ОА2 формирует уже сами признаки – слово F=(S, Z, P, C, C’) в соответствии с логикой признаков, которая задается таблично для каждой отдельной операции (см. табл. 1.10 ). Операции, реализуемые ОА (рис. 1.22), инициализируются управляющим сигналами. Поскольку операции y 1 , y 2 ,… несовместимы во времени, в текущий момент t только один из управляющих сигналов может быть равен 1, а остальные равны 0.

Рис. 1.23. Структурное представление ОА1 и ОА2

Методика синтеза ОА1

Различают два подхода к синтезу ОА1. При первом ОА1 рассматривают как единый 4-разрядный операционный элемент (ОЭ), при втором – как композицию одноразрядных (рис. 1.25, а) либо двухразрядных ОЭ (рис. 1.25, б). Два подхода обусловили две методики формирования кодированных таблиц (КТ), описывающих поведение автомата.

Рис. 1.24. Классификация операций

Рис. 1.25. Представление ОА

Рис. 1.26. Структура ОА1

ОА1 как единый 4-разрядный ОЭ

Стандартное описание автомата при таком подходе, т.е. методику формирования КТ, рассмотрим на примерах автоматов ОА 1 (0) и ОА 1 (1) с памятью на DС-триггерах, реализующих соответственно:

— операцию циклического сдвига влево через флажок переноса С (рис.1.27, а), инициируемую сигналом y 0 (табл. 1.10) и

— операцию декремента (А←А-1) в коде «2421» (рис. 1.27, б), инициируемую сигналом y 1.

Рис. 1.27. Абстрактное

Автомат ОА 1 0 (рис. 1.27, а) описывается функциями переходов A(t+1)=δ 0 (с,A(t))= δ 0 (c, a 3 a 2 a 1 a 0 ) и выходов f c 0 =f c 0 (с,A(t))= f c (c, a 3 a 2 a 1 a 0 ), которые и определяют структуру совмещенной КТ переходов, выходов и функций возбуждения (табл. 1.11). Каждой паре «С(t)–A(t)» ставится в соответствие двоичный вектор следующего состояния автомата A(t+1)=a 3 * a 2 * a 1 * a 0 * как результат функции перехода δ 0 операции y 0 : (А←2А+С).

Некоторые подзадачи задачи вершинной минимизации недетерминированных конечных автоматов Текст научной статьи по специальности « Автоматика. Вычислительная техника»

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Кукеев Максим Владимирович, Мельников Борис Феликсович,

Текст научной работы на тему «Некоторые подзадачи задачи вершинной минимизации недетерминированных конечных автоматов»

Некоторые подзадачи задачи вершинной минимизации недетерминированных конечных автоматов

М.В. Кукеев, Тольяттинский государственный университет, аспирант, unleavened@yandex. гы;

Б.Ф. Мельников, Тольяттинский государственный университет, профессор, доктор физико-математических наук, ВМеШЫу@№ы. гы

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

В современных условиях возникают задачи построения минимального по какому-либо критерию недетерминированного конечного автомата. Вершинная минимизация позволяет минимизировать состояния конечного автомата. Это полезно, например, для компактного представления этого автомата в памяти компьютера.

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

В данной работе используется модель параллельного вычисления, основанная на архитектуре CUDA (Compute Unified Device Architecture — унифицированная архитектура вычислений) [1], которая является перспективной во многих научных направлениях. И, хотя появилась на рынке эта архитектура сравнительно недавно (примерно в 2006 году), уже сейчас она активно внедряется в научные «круги».

Использование архитектуры CUDA в задачах с объёмными вычислениями часто даёт приличный прирост производительности, а если уж задача изначально располагает к параллелизму, то равных архитектуре CUDA по параметру цена/производительность нет.

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

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

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

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

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

Для определения того, что найденный автомат не задает исходный язык, будем найденные циклы, не включающие в себя подциклы, базисного автомата «искать» (в программе — проверять) в полученном автомате. Если цикл отсутствует — автомат не подходит, и следует выбрать другое покрывающее множество блоков. Это утверждение верно, так как если в покрывающем автомате отсутствует хотя бы один цикл, то найдётся слово данного языка, прочитывая которое, базисный автомат «проходит» цикл (причём, может быть и не один раз, в зависимости от выбранного слова), отсутсвующий в покрывающем автомате. Разбив это слово на три части: преффикс, без учёта той части, которая распознаётся рассматриваемым циклом, часть, распознаваемая циклом, и оставшийся суффикс, и прочитав преффикс, базисный автомат окажется в одном или нескольких из своих состояний. Значит, покрывающий автомат, по определению, должен оказаться в одном или нескольких из своих состояний, включающих состояния, в которых оказался базисный автомат. Аналогично с суффиксной частью. Ввиду однозначности базисного автомата существует только единственная последовательность тактов базисного автомата, распознающая данное слово, значит «верным» окажется только одно единственное состояние базисного автомата, в которое он попадёт после прочтения преффикса, и с которого будет начато чтение суффикса. Следовательно, опираясь на построение покрывающего автомата, мы можем утверждать, что он также содержит этот цикл.

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

Анализ подзадач для их дальнейшей алгоритмизации

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

Рассмотрим первую подзадачу.

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

Дан ориентированный граф с помеченными дугами. Требуется найти множество всех его циклов, не включающих подциклы. Такая задача уже давно решена. Существует несколько алгоритмов её решения. Однако, до сих пор не существует эффективного алгоритма её решения,

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

Вообще говоря, первый алгоритм, рассматриваемый мной, в теории графов придуман для неориентированных графов. Однако, делая небольшие поправки в этот алгоритм, мы получаем требуемый результат. Опишем сначала исходный вариант алгоритма [6, с. 95].

Шаг 1: строим остовное дерево на основе нашего графа.

Шаг 2: перебираем все дуги, не вошедшие в остовное дерево.

Шаг 3: добавляя одну дугу к дереву, получаем в точности один цикл, не содержащий подциклов.

Шаг 4: выписываем получившиеся циклы.

Сложность этого алгоритма без учёта шага 4 — 0(т * п) [5, с. 91], где т — количество дуг, а п — количество вершин. Под сложностью здесь понимается асимптотичесткая (т. е. в пределе) верхняя граница.

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

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

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

Так как понятие остовного дерева для ориентированного графа не определено, следует пояснить значение шага 1. Мы хотим найти такой подграф, содержащий все вершины исходного графа, что добавление любой не вошедшей в него дуги образует цикл (в терминах ориентированного графа — контур). Это позволит нам не рассматривать всё множество вершин. Забегая вперёд, можно сказать, что мы будем искать выходящее дерево (другое название — корневое дерево) [9, с. 235] в нашем графе, причём максимальное. То есть, невозможно добавить дугу к дереву, не нарушив его свойств. Таким образом мы минимизируем количество дуг, не вошедших в корневое дерево. Корневое дерево — это ориентированный граф с источником, не имеющий полуконтуров [9, с. 233]. Источником в графе называется вершина, из которой можно достичь все другие вершины графа.

А теперь, собственно, покажем, почему этот алгоритм в исходном виде не подходит для нашего графа. В случае неориентированного графа нам всё равно, откуда начинать строить остовное дерево, однако в ориентированном графе далеко не из каждой вершины можно обойти весь граф. А нам это необходимо для нахождения корневого дерева. Значит в нашем случае имеет значение, откуда начинать построение корневого дерева. Так как базисный автомат не содержит бесполезных и недостижимых состояний, то, очевидно, начав построение со стартовых состояний, мы гарантированно пройдём по всем возможным вершинам и дугам. Следовательно, вершины, соответствующие всем стартовым состояниям базисного автомата, образуют источник. Есть ещё несколько ньюансов, появившихся в результате ориентированности графа: если в неориентированном графе мы пытались присоединить к текущему дереву уже присоединённую вершину, то сразу же натыкались на образование цикла. Это очевидно, ведь обе рассматриваемые вершины входят в дерево, а значит существует путь между этими вершинами. Стоит только добавить дугу, соединяющую эти вершины, мы сразу получаем цикл. В ориентированном графе в вершину может входить сколько угодно дуг, циклы от этого не появятся. Важно, выходят ли из этой вершины дуги; если да, то при тех же условиях, что и в неориентированном графе, возможно появление цикла. Но для этого должен существовать путь между рассматриваемыми вершинами. В ориентированном графе это далеко не очевидно: если две вершины входят в дерево, это не значит, что между ними существует путь, это значит, что точно существует путь из начально рассмотренной вершины в эти вершины. Следовательно, возникает вопрос, как тогда определять появление цикла. Выше мы уже оговорились, что будем строить максимальное корневое дерево. Для его построения, фактически, используется простой алгоритм для нахождения остовного дерева для неориентированного графа [5, с. 646]. После работы такого алгоритма мы получим лишние дуги, то есть такие, добавление которых к корневому дереву не приводит к появлению контура. Чтобы не делать повторных вычислений, немного модифицируем задачу. В определении корневого дерева заменим понятие полуконтур на контур. Соответственно, изменим и алгоритм для решения обновлённой задачи.

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

добавляемой вершины в текущую, и добавлять дугу нельзя. В противном случае добавляем дугу и обновляем множество вершин, из которых мы можем попасть в рассматриваемую, для всех вершин, в которые существует путь из добавленной вершины. Таким образом, мы гарантированно построим корневое дерево с вышеперечисленными поправками для ориентированного графа, построенного на основе базисного автомата. Данный алгоритм затрачивает дополнительное время при выполнении по сравнению с предыдущим, но существенным образом это не влияет на эффективность. Гораздо важнее то, что мы избавились от лишних дуг. Ведь дальше нам потребуется для каждой такой дуги искать контуры, проходящие через неё. С учётом неэффективности всех алгоритмом поиска всех контуров графа, лишние дуги гораздо сильнее замедлят работу программы, нежели дополнительные вычисления в изменённом алгоритме поиска корневого дерева.

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

Найдя все возможные дуги, добавление которых приводит к образованию цикла, будем искать в исходном графе все пути из одной вершины в другую, соответствующие рассматриваемой дуге. Для поиска пути можно использовать, например, алгоритм поиска в ширину или в глубину, сложность которых составляет 0(т + п), где т -количество дуг, а п — количество вершин графа, в котором осуществляется поиск. Важно то, что сложность алгоритмов поиска в ширину и в глубину дана для нахождения одного пути в графе.

Рассмотрим вторую подзадачу.

При её решении никаких трудностей не возникает. Для каждого найденного контура, проверяем его наличие в покрывающем автомате. Сложность проверки каждого контура — О(п), где п — количество состояний базисного автомата. Оценка верна, так как при проверки контура мы делаем т + 1сравнений, где т — количество вершин в контуре. Очевидно, что т i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Обзор архитектуры CUDA

Современные GPU третьего поколения содержат набор одинаковых вычислительных устройств — «потоковых процессоров» (ММ), работающих с общей памятью GPU (видеопамять). Число ММ меняется от 4 до 128, размер видеопамяти может достигать 1 Гбайт. Все ММ синхронно исполняют один и тот же шейдер — программу специального вида, написанную на шейдерном языке, что позволяет отнести GPU к классу SIMD (Single Instruction, Multiple Data). SIMD представляет из себя принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. За один проход, являющийся этапом вычислений на GPU, шейдер исполняется для всех точек двухмерного массива. Система команд ММ включает в себя арифметические команды для вещественных и целочисленных вычислений с 32-разрядной точностью, команды управления (ветвления и циклы), а также команды

обращения к памяти. GPU выполняют операции только с данными на регистрах, число которых может достигать 128. Из-за высоких задержек (до 500 тактов) команды доступа к оперативной памяти выполняются асинхронно. С целью скрытия задержек в очереди выполнения GPU может одновременно находиться до 512 потоков, и, если текущий поток блокируется по доступу к памяти, на исполнение ставится следующий. Поскольку контекст потока полностью хранится на регистрах GPU, переключение осуществляется за один такт — за эту операцию отвечает диспетчер потоков, который не является программируемым.

Архитектура GPU семейства nVidia последних поколений представлена на рисунке 1. Вообще говоря, она не является классическим представителем архитектур SIMD. В ней 128 IIII объединены в SIMD-группы по 16 мультипроцессоров (МП), но при этом разные МП работают независимо друг от друга, хотя и исполняют один и тот же шейдер. Каждый IIII является суперскалярным (возможность выполнения более одной команды за такт) устройством и может выполнять до двух команд за такт. При обращении в видеопамять ему доступна вся память, как на чтение, так и на запись. Однако на практике ввиду слабости средств синхронизации между различными МП желательно процесс обработки строить так, чтобы адреса записи не пересекались.

Рис.1. Архитектура GPU семейства nVidia GeForce 8 В GPU программисту доступны 16 Кбайт явно адресуемой статической памяти на мультипроцессоре, которая используется совместно всеми ММ одного мультипроцессора, имеющего внутри механизм барьерной синхронизации потоков. Заметим, что грамотное использование статической памяти как раз и является ключом к написанию эффективных программ для данной архитектуры.

Важно, что все потоки одного блока всегда выполняются одним и тем же мультипроцессором. А потоки из разных блоков обмениваться данными не могут, и нужно помнить это ограничение. Разделяемая память часто бывает полезной, кроме тех случаев, когда несколько потоков обращаются к одному банку памяти. Мультипроцессоры могут обращаться и к видеопамяти, но с большими задержками и худшей пропускной способностью. Для ускорения доступа и снижения частоты обращения к видеопамяти, у мультипроцессоров есть по 8 килобайт кэша на константы и текстурные данные.

Статистическое сравнение результатов

Объективно сравнить результаты выполнения алгоритмов на центральном процессоре и графическом процессоре крайне сложно, а

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

Для полноты сравнения приведём тестовые конфигурации, на которых выполнялись программы. Аппаратная часть состоит из центрального процессора Intel Core 2 Duo E6550 с частотой 3.0 Гц и двумя ядрами, из 4 Гб оперативной памяти DDR2 с частотой 800 МГц, графической платы nVidia GeForce GTX 260 с частотой потоковых процессоров 1242 МГц, частотой GPU — 576 МГц, с количеством потоковых процессоров — 192. Все действия выполнялись под управлением операционной системы Microsoft Windows 7 64 bit. Версия драйверов графической карты — 2.3, архитектура — 1.1.

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

Для получения различных статистических данных будем менять различные характеристики исходных данных. Количество состояний базисного автомата, количество стартовых состояний базисного автомата. «Плотность» «дуг» базисного автомата, т.е. разная вероятность соединения двух состояний «дугой». Отдельно посмотрим на время выполнения проверки циклов базисного автомата в покрывающем автомате.

Результаты работы программ

Посмотрим время выполнения алгоритма построения «остовного дерева» с различными параметрами.

Для начала сделаем вероятность наличия перехода между двумя состояниями 0.5. Здесь стоит заметить, что, хоть и подразумевается генерирование базисного автомата, фактически, мы получаем произвольный автомат. Генерирование базисного автомата представляет из себя задачу для отдельной работы. Такое ослабление не изменит общую картину сравнительной статистики. Количество стартовых состояний пока сделаем равным 2.

Результаты вычислений находятся в таблице 1.

Кол-во состояний базисного автомата CPU, мс GPU, мс

Количество состояний ограничено числом 240, так как константная память графического акселератора ограничена. Как видно из таблицы, увеличение количества состояний базисного автомата в меньшей степени влияет на время вычисления. Этого стоило ожидать в виду параллельности графического акселератора. Интересным оказалось то, что при увеличении стартовых состояний базисного автомата производительность на GPU даже немного ухудшилась, хотя теоретически она должна была только увеличиться. Видимо, много времени уходит на синхронизацию потоков при конфликтных ситуациях.

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

Кол-во состояний базисного автомата CPU, мс GPU, мс

Как мы и ожидали, графический процессор «потерял» больше времени, нежели центральный, однако всё равно сохраняет приличное преимущество.

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

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

Оставляем параметры предыдущих тестов.

Кол-во состояний CPU, мс GPU, мс

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

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

Кол-во состояний базисного автомата CPU, мс GPU, мс

Предположения оправдались. Графический акселератор с увеличением состояний, больше выигрывает у центрального процессора, так как быстрее проверяет циклы. Использование памяти при этом минимально, а значит и задержки минимальны. Такие задачи изначально подходят для параллельной реализации, что и подтверждает статистика. Ограничение в 512 состояний можно убрать, немного модифицировав алгоритм нахождения корневого дерева, однако это не имеет большого значения, так как нахождение циклов не является эффективным.

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

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

1. Берилло, А. NVIDIA CUDA — неграфические вычисления на графических процессорах [Электронный ресурс]. URL: http://www.ixbt.com/video3/cuda-l.shtml (дата обращения: 07.10.2009).

2. Богомолов, С. Использование модели массового параллелизма CUDA для разработки программ [Электронный ресурс]. URL: http://www.bog.pp.ru/work/cuda.html (дата обращения: 12.01.2010).

3. Брауэр В. Введение в теорию конечных автоматов ; под ред. чл.-корр. АН СССР Ю. И. Журавлева ; пер. с нем. К. В. Рудакова. — М.: Радио и связь, 1987. — 392 с.

4. Вишняков С. М., Ковальчук С. В., Бухановский А. В. Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов // Параллельные вычислительные технологии (ПаВТ 2008): Труды международной научной конференции (Санкт-Петербург, 28 января — 1 февраля 2008 г.). — Челябинск: Изд. ЮУрГУ, 2008. — с. 340-346.

5. Кормен Т. [и др.] Алгоритмы: построение и анализ ; пер. с англ.. — 2-е изд. -М.: Вильямс, 2005. — 1296 с.

6. Липский В. Комбинаторика для программистов ; пер. с пол. В. А. Евстигнеева и О. А. Логиновой ; под ред. А. П. Ершова. — М.: Мир, 1988. -200 с.

7. Мельников Б. Ф. Недетерминированные конечные автоматы ; монография. -Тольятти: ТГУ, 2009. — 160 с.

8. Мотвани Р., Ульман Д., Хопкрофт Д. Введение в теорию автоматов, языков и вычислений ; пер. с англ.. — 2-е изд. — М.: Вильямс, 2002. — 528 с.

9. Харари Ф. Теория графов ; пер. с англ. В. П. Козырева ; под ред. Г. П. Гаврилова. — 2-е изд. — М.: Едиториал УРСС, 2003. — 296 с.

Конечные автоматы (стр. 5 )

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8

Глядя на таблицу переходов, изображенную на рис. 2.23, мы замечаем, что не надо делать различия между ролями Л1 и Л2, а также a1 и A2. Алгоритм позволяет нам не заботиться об этом при создании исходного распознавателя.

Н С Л О А Ь

Рис. 2.23.

Хотя процедура гарантирует, что детерминированный автомат не содержит недостижимых состояний, детерминированный автомат может оказаться не минимальным. В последнем примере состояния <О>и <Ь>явно эквивалентны и могут быть объединены.

Тема3. Реализация конечных автоматов

3.1 Введение

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

На протяжении этой главы рассматриваются три взаимосвязанных вопроса:

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

2. как справиться с некоторыми специфическими проблемами, постоянно возникающими при компиляции,

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

Некоторые задачи, решаемые с помощью конечных автоматов, заключаются всего лишь в распознавании конечного множества слов. Суть этих проблем в том, что компилятор должен обнаружить появление некоторого слова из такого множества и затем действовать в зависимости от того, какое это слово. Операторы MINI-BASIC’a, например, могут начинаться с одного из девяти слов (LET, IF, GOTO и т. д.), и для компилятора важно установить, с какого из них (если оно есть) начинается строка, и предпринять действия, соответствующие данному типу оператора. Задачу такого характера мы называем проблемой «идентификации», так как действия компилятора зависят от идентичности некоторому известному слову данного слова, включенного в входную цепочку автомата. Так как для решения задач идентификации может потребоваться огромное число состояний, в подобных случаях часто приходится пользоваться специальными методами реализации. По этой причине нередко рекомендуется строить компилятор так, чтобы проблема идентификации решалась отдельным подпроцессором, специально предназначенным для этого.

Существуют проблемы идентификации, которые, строго говоря, не могут быть решены с помощью конечного автомата. Обратимся к часто встречающейся проблеме распознавания переменных или идентификаторов некоторого языка и соотнесения их с соответствующими элементами таблицы имен. Решение этой проблемы обычным методом с помощью конечного автомата потребует нескольких состояний и элемента таблицы имен для каждого допустимого идентификатора. Однако множество допустимых идентификаторов в большинстве языков бесконечно или так велико, что его вполне можно считать бесконечным. В Алголе, например, где идентификатор может состоять из произвольного числа символов, множество допустимых идентификаторов бесконечно, тогда как в Фортране, где длина идентификатора не больше шести, число допустимых идентификаторов конечно, но астрономически велико, так что на практике считается бесконечным. (В противоположность этому идентификаторы MINI-BASIC’a могут состоять не более чем из двух символов, поэтому число допустимых идентификаторов конечно и поддается обработке.)

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

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

3.2. Представление входных символов

Чтобы смоделировать конечный автомат, мы должны каким-нибудь подходящим способом закодировать его входное множество. Наиболее гибкое решение состоит в представлении входного множества с помощью набора последовательных целых чисел, начиная с 0 или 1. Это кодирование хорошо работает во всех рассматриваемых далее способах реализации переходов автомата. Однако некоторые из этих способов работают также и при произвольном кодировании входного множества.

Рис. 3.1.

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

Если бы множество символов исходной программы непосредственно служило входом для некоторого конечного процессора, содержащего много состояний, то автомат имел бы большую таблицу переходов, так как одни только цифры и латинские буквы образуют множество из 36 символов, обычно же множество символов в несколько раз больше. Удобный способ уменьшения размера таблицы переходов заключается в обработке исходных символов двумя последовательно соединенными автоматами: первый автомат — это транслитератор, единственная задача которого — сократить входное множество до приемлемых размеров; второй автомат выполняет остальную часть работы. Этот вид взаимодействия показан на рис. 3.1, а.

Зависимость между входом и выходом транслитератора можно выразить с помощью таблицы, например, такой, как на рис. 3.1, б, которая содержит перевод каждого символа исходного языка. Выход этого транслитератора будем называть символьной лексемой. Такая лексема обычно состоит из двух частей: класса и значения. Так, буква а будет иметь класс БУКВА и значение а, тогда как знак операции + имеет класс ОПЕРАЦИЯ и значение +. Класс лексемы должен служить входом для второго автомата, а ее значение доступно процедурам переходов этого автомата. Потребность в такой предварительной обработке упоминалась в гл. 2. (Вспомним, например, обработку констант).

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

3.3. Представление состояний

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

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

3.4. Выбор переходов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

что означает: «из состояния по символу или по пустой цепочке (тогда ) можно перейти в состояние » (возможно, что ).

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

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

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

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

Пример 7.7. Зададим конечный автомат с входным алфавитом и множеством состояний такой системой команд:

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

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

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

Эта ситуация демонстрирует как раз недетерминированность конечного автомата как распознающего устройства: система команд («правила игры») позволяет автомату допустить цепочку («игроку» найти последовательность ходов, ведущую к «выигрышу»), но из этого вовсе не следует, что последовательность конфигураций, которую проходит автомат, читая записанную на ленте цепочку, является единственной. Автомат может «ошибиться», сделав «неправильный» ход. Но и последовательность «правильных» ходов может быть не единственной. Например, читая последний символ цепочки, т.е. символ , автомат мог «выбрать» переход в состояние , которое также является заключительным. Рассматриваемый автомат допускает не всякую цепочку в алфавите . Видно, что ни одна цепочка, которая начинается с префикса , не будет допущена автоматом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Система команд есть конечное множество команд вида , где и — состояния автомата; — входной символ или пустая цепочка, причем указанная команда тогда и только тогда содержится в системе команд, когда .

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

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

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

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

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

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

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

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

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

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

что означает, что эта метка есть множество цепочек .

*Умножением полукольца является соединение языков.

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

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

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

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

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

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

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

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

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

конечные автоматы в задачах обработки текстов. Конечные автоматы в задачах обработки текстов

Название Конечные автоматы в задачах обработки текстов
Родительский файл 3-avtomat.zip
Анкор конечные автоматы в задачах обработки текстов
Дата 11.03.2007
Размер 72.5 Kb.
Формат файла
Имя файла 3-avtomat.doc
Тип Урок
#1474
Каталог algoritm_struktura
Полное содержание архива конечные автоматы в задачах обработки текстов:
1. 3-avtomat.doc
72.5 Кб.
Конечные автоматы в задачах обработки текстов

УРОК №3
ТЕМА «Конечные автоматы в задачах обработки текстов»

рассмотреть алгоритмы обработки текстов.

изучить алгоритмы обработки текстов; реализовать эти алгоритмы на языке программирования; научиться применять эти алгоритмы при решении задач;

развитие алгоритмического мышления, способностей к формализации, элементов системного мышления;

воспитание чувства ответственности за результаты своего труда.

Материалы и оборудование к уроку:

Форма проведения урока:

УРОК №3
ТЕМА «Конечные автоматы в задачах обработки текстов»

1. Конечные автоматы и обработка текстов

1. Конечные автоматы и обработка текстов

1. В тексте возведение в степень обозначалось двумя идущими подряд звездочками. Решено заменить это обозначение на ‘^’ (так что, к примеру, ‘x**y’ заменится на ‘x^y’). Как это проще всего сделать? Исходный текст читается символ за символом, получающийся текст требуется печатать символ за символом.

Решение. В каждый момент программа находится в одном из двух состояний: «основное» и «после звездочки»

Состояние Очередной входной символ Новое состояние Действие
основное * после нет
основное x <> ‘*’ основное печатать x
после * основное печатать ‘^’
после x <> ‘*’ основное печатать *, x

Если в конце текста программа оказывается в состоянии «после», то следует напечатать звёздочку (и кончить работу).
Замечание. Наша программа заменяет ‘***’ ‘^*’ (но не на ‘*^’). В условии задачи мы не оговаривали деталей, как это часто делается — предполагается, что программа «должна действовать разумно». В данном случае, пожалуй, самый простой способ объяснить, как программа действует — это описать её состояния и действия в них.

2. В паскале комментарии заключаются в фигурные скобки:

i:=i+1; <увеличиваем i на 1>
Написать программу, которая удаляла бы комментарии и вставляла бы вместо исключенного комментария пробел (чтобы ‘1<один>2′ превратилось не в ’12’, а в ‘1 2’).
Решение. Программа имеет два состояния: «основное» и «внутри комментария».

Состояние Очередной входной символ Новое состояние Действие
основное < внутри нет
основное x <> ‘<' основное печатать x
внутри > основное печатать пробел
внутри x <> ‘>’ внутри нет

Замечание. Эта программа не воспринимает вложенные комментарии: строка вроде ‘ <<комментарий внутри>комментария>’ превратится в ‘ комментария>’ (в начале стоят два пробела). Обработка вложенных комментариев конечным автоматом невозможна (нужно «помнить число скобок» — а произвольное натуральное число не помещается в конечную память).

2. Задачи.

1. Написать программу, удаляющую из текста все подслова вида ‘abc’.

2. В паскалевских программах бывают также строки, заключенные в кавычки. Если фигурная скобка встречается внутри строки, то она не означает начала или конца комментария. В свою очередь, кавычка в комментарии не означает начала или конца строки. Как изменить программу, чтобы это учесть?

Указание. Состояний будет три: основное, внутри комментария, внутри строки.

Состояние Очередной входной символ Новое состояние Действие
основное < внутри ком. нет
основное x <> ‘ <' и x <>»» основное печатать x
основное внутри строки печать ‘
внутри ком. > основное печатать пробел
внутри ком. x <> ‘>’ внутри ком. нет
внутри строки основное печать ‘
внутри строки x<>»» внутри строки печать x

3. Еще одна возможность многих реализаций паскаля – это комментарии вида

i:=i+1; (* here i is increased by 1 *)

при этом закрывающая скобка должна соответствовать открывающей (то есть < . *) не разрешается). Как удалять такие комментарии?

Состояние Очередной входной символ Новое состояние Действие
основное ( после ( нет
основное x <> ‘(‘ основное печатать x
после ( ( после ( печать (
после ( * внутри ком. нет
после ( x<>* и x<>( основное печать (, x
внутри ком. * после * нет
внутри ком. x<>* внутри ком. нет
после * * после * печать *
после * ) основное печать пробел
после * x<>* и x<>) внутри ком. печать *, x

Литература:

  1. Шень А. Программирование: теоремы и задачи. — 2-е изд., испр. и доп. — М.: МЦНМО, 2004. —296 с.: ил.
  2. В.М. Котов, И.А. Волков, А.И. Лапо Методы алгоритмизации. Учебное пособие для 9 класса общеобразовательной школы с углубленным изучение информатики. — Мн. ИГП «Нар. асвета», 1997. — 160 с.: ил.
  3. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М.: Наука, 1988.

Глава 3. Конечные автоматы

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

В результате изучения материала этой главы читатель должен усвоить:

общее представление о конечноавтоматных преобразователях информации и их свойствах, методах их задания, особенностях двух основных типов конечноавтоматных преобразователей: автоматах Мили и Мура;

проблемы минимизации и проверки эквивалентности конечных автоматов;

методы реализации конечноавтоматных преобразователей;

примеры применения КА в различных областях и методы графического формализма конечноавтоматного представления систем обработки информации;

автоматные модели параллельных процессов

Содержание главы 3:

Автоматное преобразование информации

Эквивалентность КА: теорема Мура

Автоматы Мили и Мура

Схема управления микрокалькулятором

Протокол выбора лидера в распределенной системе

Визуальный формализм представления моделей систем с памятью: Statecharts

Автомат, регулирующий пешеходный переход

Графы переходов при спецификации и анализе параллельных программ

Проблема умножения: алгоритм, который не может выполнить КА

3.1 Автоматное преобразование информации

Не все окружающие нас преобразователи информации выполняют функциональное отображение информации. Результат преобразования входвыход зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, от предыстории преобразования. Огромное множество примеров тому дают биологические системы: например, один и тот же вход — извинение после того, как вам наступили на ногу в переполненном трамвае — вызовет у вас одну реакцию в первый раз и совсем другую в пятый раз, если вам постоянно наступают на ногу и извиняются. Таким образом, существуют более сложные, не функциональные преобразователи информации, реакция их зависит не только от входа в данный момент, но и от входной истории. Такие преобразователи называются автоматами. Даже если различных элементов входной информации у автомата конечное число (как в конечном функциональном преобразователе), количество возможных входных историй бесконечно (счетно). Если автомат по разному будет себя вести в дальнейшем для всех или бесконечного числа возможных предысторий, то такой “бесконечный” автомат должен иметь бесконечный ресурс — память, чтобы все эти предыстории запоминать. Объединим все “эквивалентные” предыстории в классы эквивалентности: две истории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Таким образом, автомат, реализующий не функциональное отображение, должен обладать памятью для запоминания входных историй или, как минимум, классов эквивалентности, к которым принадлежат истории. Случай, когда число классов эквивалентных входных историй конечно, является простейшим, однако, он вызвал значительный интерес и имеет очень широкие применения. Такая модель называется конечным автоматным преобразователем информации, или просто конечным автоматом.

Определение 3.1. (Внутренним) состоянием дискретного преобразователя назовем класс эквивалентности его входных историй.

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

Рис. 3.1. Автоматный преобразователь и его реализация

Пример 3.1.Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Граф автомата, моделирующего умное поведение родителя, представлен на рис. 3.2.

Рис. 3.2. Автомат, описывающий поведение отца

Здесь конечный автомат изображен графом с вершинами, соответствующими состояниям. Ребра графа соответствуют переходам между состояниями. Ребро помечено входным сигналом, под воздействием которого этот переход происходит, и выходным сигналом, который вырабатывает автомат при получении этого входного сигнала в текущем состоянии. Автомат, моделирующий родителя, имеет четыре состояния , и два входных сигнала — оценки, полученные сыном в школе: <2, 5>. Начиная с начального состояния s0 (оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы — реакции на входы. Выходы автомата будем интерпретировать как действия родителя так:

у0: — брать ремень;

у1: — ругать сына;

у2: — успокаивать сына;

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

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

Определение 3.2. Конечным автоматом Мили называется шестерка объектов: А= , где:

S — конечное непустое множество (состояний);

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

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

sS — начальное состояние;

: SXS — функция переходов;

: SXY — функция выходов.

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

Гилл А. Введение в теорию конечных автоматов (с распознанным текстом)

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

Примечания.
Объем 21 мб. Формат — doc (2003). Текст книги распознан (в том числе обозначения переменных, состояний, нижние индексы и т. д. ), то есть может без дополнительной обработки редактироваться и частично вставляться в работы и статьи.

Полное содержание работы.
1. ОСНОВНАЯ МОДЕЛЬ
1.1 Введение
1.2 Многополюсный черный ящик
1.3 Дискретность времени
1.4 Конечность алфавита
1.5. Состояния
1.6. Определение основной модели
1.7. Примеры конечных автоматов
1.8. Определение множества состояний по внутренней структуре
1.9. Другая модель
1.10. Предсказание поведения автомата
2. ТАБЛИЦЫ, ГРАФЫ И МАТРИЦЫ ПЕРЕХОДОВ
2.1. Введение
2.2. Таблица переходов
2.4. Изоморфные автоматы
2.5. Граф переходов
2.6. Классификация состояний и подавтоматов
2.7. Разложение автоматов и расщепляемый автомат
2.8. Матрица переходов
2.9. Матрицы переходов высшего порядка
2.10. Элементарные пути
2.11. Определение минимальных путей и полных контуров
2.12. Скелетная матрица
2.13. Частичное построение матриц
3. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ
3.1. Введение
3.2. Эквивалентность состояний
3.3. k-эквивалентность
3.4. k-эквивалентные разбиения
3.5. Эквивалентные разбиения
8.6. Разбиение при помощи таблиц Рk
3.7. Разбиение при помощи таблицы пар
8.8. Матричный метод разбиения
3.9. Эквивалентность автоматов
8.10. Эквивалентное разбиение множеств автоматов
3.11. Минимальная форма
3.12. Свойства минимальной формы
3.13. Уменьшение числа состояний автомата последовательным объединением
3.14. Класс минимальных автоматов
4. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ
4.1. Введение
4.2. Классификация экспериментов
4.3. Диагностические и установочные эксперименты
4.4. Диагностические эксперименты для двух состояний
4.5. Разновидности диагностической задачи с двумя состояниями
4.6. Дерево преемников
4.7. Диагностическое дерево
4.8. Простые безусловные диагностические эксперименты
4.9. Простые условные диагностические эксперименты
4.10. Кратные безусловные диагностические эксперименты
4.11. Кратные условные диагностические эксперименты
4.12. Установочное дерево
4.13. Простые безусловные установочные эксперименты
4.14. Простые условные установочные эксперименты
4.15. Регулярные безусловные установочные эксперименты
4.16. Регулярные условные установочные эксперименты
4.17. Следствия, связанные с экспериментами по распознаванию состояний
5. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ АВТОМАТОВ
5.1. Введение
5.2. Общая задача распознавания автомата
5.3. Распознавание автоматов известного класса
5.4. Задача распознавания повреждений
5.5, Сильносвязные автоматы
5.6. Некоторые свойства сильносвязных автоматов
5.7. Распознавание сильносвязных (n, р, q)-автоматов
5.8. Автоматы без потери информации
6. АВТОМАТЫ С КОНЕЧНОЙ ПАМЯТЬЮ
6.1. Введение
6.2. Представление систем с конечной памятью
6.3. Свойства автоматов с конечной памятью
6.4. Определение памяти автомата
6.5. Минимальная x-z-функция
6.6. Линейные двоичные автоматы
6.7. Временная характеристика линейного двоичного автомата
6.8. Распознавание линейного двоичного автомата
6.9. Не зависящие от выхода автоматы
7. АВТОМАТЫ С ОГРАНИЧЕНИЯМИ НА ВХОДЕ
7.1. Введение
7.2. Совместимость состояний
7.3. Квазиэквивалентные автоматы
7.4. Определение минимальных форм
7.5. Метод уменьшения числа состояний автоматов с ограничениями на входе

Илон Маск рекомендует:  Пример простейшего сниффера для w2kxp
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL