Базисные конечные автоматы

• Автор: Мельникова, Александра Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Димитровград
• Количество страниц: 102 с. : ил.

Оглавление
1 Введение
1.1 Исторический обзор, актуальность
и новизна темы
1.2 Применяемые обозначения
1.3 Структура диссертационной работы
2 Базисные автоматы — определения
2.1 Дополнительные определения и обозначения
2.2 Базисный автомат - определение
2.3 Функции разметки состояний
2.4 Первый пример построения
2.5 Основное утверждение
2.6 Однозначность базисного автомата
2.7 Свойство допускающего пути произвольного ПК А
2.8 Примеры построения базисного автомата
2.9 Альтернативный алгоритм
3 Свойства базисных автоматов
3.1 Свойства функций разметки
3.2 Варианты алгоритмов объединения состояний
3.3 Примеры применения
3.4 Изменение значений функций разметки
3.5 Свойства входных и выходных языков
3.6 Ещё раз о бинарном отношении #
4 Задачи минимизации
4.1 Блоки и псевдоблоки

ОГЛАВЛЕНИЕ
4.2 Множество возможных дуг
4.3 Первый алгоритм дуговой минимизации
4.4 Второй алгоритм дуговой минимизации
5 Заключение
Литература
Глявэ.
Введение
1.1 Исторический обзор, актуальность и новизна темы
Исторический обзор
Недетерминированные конечные автоматы (ниже - НКА), изучаемые в диссертационной работе, впервые рассматривались в середине прошлого века Ю. Медведевым ([21]), а также М. Рабином и Д. Скоттом ([102]). Позднее, прежде всего - при применении НКА к решению различных прикладных задач, указанные автоматы модифицировались и обобщались многими авторами (см., например [10, 57, 58, 67, 90, 91]). По-видимому, самым важным их обобщением стали недетерминированные автоматы-распознаватели с магазинной памятью (push-down automata, МП-автоматы), появившиеся как одно из средств автоматического перевода, а также для различных целей программирования, широко используемые в теории трансляции ([1, 2, 3]. Как МП-автоматы, так и НКА служат примером так называемых автоматов-распознавателей - в отличие от конечных автоматов-преобразователей (например, конечных автоматов Мили, Мура), которые в представляемой диссертационной работе не рассматриваются. Конечные автоматы и такие тесно связанные с ними конструкции, как, например, линейные грамматики и регулярные выражения, относятся к основным понятиям информатики.

ГЛАВА 2. БАЗИСНЫЕ АВТОМАТЫ - ОПРЕДЕЛЕНИЯ
Доказательство. Рассмотрим две разные последовательности состояний множества <Э -
0Э » 01 > • • • ?т И ?0 > ?1 > • • ' 0п (2-9)
- определяющих одно и то же слово и Е £(ЛТ) (согласно условию утверждения, такие последовательности найдутся). Отметим, что до,д2 е ^ аналогично <Д, Д Е И, и, кроме того, эти последовательности имеют, вообще говоря, разную длину (поскольку мы допускаем возможность е-дуг); также отметим, что мы допускаем возможности т — 0 и п — 0.
Поскольку последовательности (2.9) различны, то существует некоторое представление слова и в виде и = щщ, причём такое, что работой автомата (1.1) при прочтении слова щ является перемещение как из до в некоторую вершину д (к Е {0,... ,то}), так и из $ в некоторую д2 (I Е { 0,...,гг}). Обозначим г = д£, г2 = д2; состояния Г и гг являются искомыми. Действительно, пусть работа автомата Ь при прочтении слова щ есть перемещение в (единственно возможную) вершину А] тогда по определению функций разметки имеем
*р}"(г 1) Э А и <Рд(г2) Э П.
Аналогично доказывается, что
Т0Лгг) Э X и <рГ(г2)эХ
для некоторой вершины А автомата Ьн, т.е. оба условия (2.8) действительно выполнены. □ ■
Теперь рассмотрим несколько простых примеров ([32] и др.). Наличие двух различных вершин, удовлетворяющих условиям (2.8), может как приводить, так и не приводить к неоднозначности автомата - т.е. условия (2.8) для неоднозначности автомата не являются достаточными. Действительно, на рис. 10 изображён неоднозначный автомат, у которого значения обеих функций разметки для вершин 2 и 3, есте-