Конечные автоматы, сложность, представление конечных автоматов, произведение

ч. 1


Функция разметки состояний и базисные слова для конечных автоматов
© 2011
Крайнюков Н.И., к.т.н., доцент, Тольяттинский государственный университет, кафедра «Прикладной математики и информатики»
nik9kr@gmail.com
Мельников Б.Ф., д. ф-м. н, профессор Тольяттинский государственный университет, кафедра «Прикладной математики и информатики»
B.Melnikov@tltsu.ru
Ключевые слова: конечные автоматы, сложность, представление конечных автоматов, произведение регулярных языков.
Аннотация: Представление конечных автоматов в виде базисных слов с использованием функции разметки и базисного автомата [2] позволяет в ряде случаев оценивать сложность языка, представить его произведения как количество состояний базисного автомата при процедуре детерминизации.
1.Введение

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


2.Основная часть
Введем необходимые определения и обозначения.

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

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

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

Конечный автомат – является детерминированным (ДКА), если он имеет одно начальное состояние и , для любых и , в противном случае, он является недетерминированным (НКА).

Для НДА , используя алгоритмы детерминизации и минимизации, можно построить минимальный детерминированный автомат , который будем называть каноническим [2].

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

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


Пример 1.

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


| 1 2 3

--------------

a | 2 2 2

b | 1 3 1

Начальное состояние: [ 1 ]

Заключительное состояние: [ 3 ]
Таб. 1. Таблица переходов автомата, допускающего язык .

Рис 1. Граф переходов автомата, построенного по таблице 1.

Представительные функции могут быть заданы следующим образом:


Состояние





1





2





3





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

Используя представительную функцию для канонического автомата легко вычислить функцию разметки [2] для любого автомата , допускающего язык :



(1)

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

С каноническим автоматом, можно связать переписывающую систему [4]. Напомним определение, переписывающая система – это пара , где - алфавит, а множество пар (они могут записываться в виде ), который называются перезаписывающими правилами/продукциями. Для слов , будем писать , если , для некоторой продукции .

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


Пример 2.

Для автомата , из примера 1, продукции перезаписывающей системы для представляющих функций , .




Состояние









1









2









3









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

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

4.Список литературы
1.Хорпкрофт Дж., Р.Мотвани, Дж. Ульман «Введение в теорию автоматов. Языков и исчислений», Из-во «Вильямс», 2008 – 528с.

2.Мельников Б.Ф. Недетерминированные конечные автоматы.Тольятти. ТГУ, 2009 – 161 с.

3.Лаллеман Ж. Полугруппы и комбинаторные приложения. – М. Мир, 1985- 440 с.

4.Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений. – М.: Мир, 2004 – 528 c.



5.Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987.-392 с.
ч. 1