Функция разметки состояний и базисные слова для конечных автоматов 2011

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

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

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

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

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

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

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

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

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

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

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

Состояние
1
2
3

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

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

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

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

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

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

Состояние
1
2
3

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

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

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

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

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