2013г.Павлов И.С.

Теория автоматов и формальных языков

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

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

Введение

1. Начальные понятия теории формальных языков

Рассмотрим непустое конечное множество А, состоящее из символов {a₁, …, a_k}. Будем называть А алфавитом, а его символы – буквами. Всякая конечная последовательность букв этого алфавита называется словом (цепочкой или строкой): w=a₁a₂…a_n – слово (a_i A), |w| – длина слова (число букв, из которых состоит слово, причем каждый символ встречается столько раз, сколько раз он встречается в w). Через |w|_b обозначим количество вхождений символа b в слово w.

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

- множество слов алфавита А длины n. Множество всех слов алфавита А (включая сверхслова) обозначается А*. Это множество счетное, поскольку является объединением счетного числа конечных множеств . Множество всех непустых слов в алфавите А обозначается А⁺. Если A={a}, то А*={a}* будем обозначать через а*.

Любое подмножество называетсяязыком (формальным языком) над алфавитом А.

Если x и y – слова языка , то слово ху (результат приписывания слова у в конце слова х) называется конкатенацией (сцеплением, произведением) слов х и у. (n раз берем х). Положим .

Говорят, что слово х – подслово слова у, если y=uxv для некоторых слов u и v. Все подслова слов языка образуютмножество подслов языка L, которое обозначается через Subw(L).

Примеры. 1. ba³=baaa, - в данном слове есть подслова ab, aba, ba и т.п.

2. Множество {a, abb} - язык (конечный) над алфавитом {a, b}.

3. Множество является языком над алфавитом {a, b}. Этот язык бесконечный, он содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa и т.д.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом. Так, язык , где, называется дополнением языкаL относительно алфавита А. И если  всегда включено в А*, то язык может как содержать, так и не содержать его. В последнем случае .

Пусть ,. Тогда языкназываетсяконкатенацией (сцеплением, произведением) языков и . При этом , (n раз), если n>0.

Примеры. 1. Если , ,то .

2. Если L={0, 01}, то .

Итерацией языка L называется язык (эта операция называется также звездочкой Клини). Язык называется позитивной итерацией языка L.

Пример. Если A={a, b} и L={aa, ab, ba, bb}, то .

Обращением или зеркальным образом слова w называется слово w^R, в котором буквы слова w идут в обратном порядке. Например, если w=bac, то

Пусть . Тогда языкназываетсяобращением языка L.

Всякое начало слова будем называть префиксом, а всякий конец слова – суффиксом. Например, если y=xv, то х – префикс слова у (обозначение – х[y), а v – суффикс слова у (обозначение – v]y). Очевидно, что пустое слово является как префиксом, так и суффиксом любого слова. Все префиксы слов языка формируютмножество префиксов этого языка: Pref(L). АналогичноSuf(L)-множество суффиксов языка .

Если язык L таков, что никакое слово L не является префиксом (суффиксом) никакого другого слова L, то говорят, что L обладает префиксным (суффиксным) свойством.

Пусть А₁ и А₂ – алфавиты. Если отображение f: удовлетворяет условиюдля всех слови, то отображениеf называется гомоморфизмом.

Замечания. 1. Можно доказать, что если f – гомоморфизм, то .

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

3. Применяя гомоморфизм к языку L, получаем другой язык f(L).

Если f: – гомоморфизм, и, то черезf(L₁) обозначается язык , а черезобозначается язык, а само отображениеназываетсяобращением гомоморфизма.

Примеры. 1. Допустим, мы хотим заменить каждое вхождение в цепочку символа 0 на символ а, а каждое вхождение 1 – на bb. Тогда можно определить гомоморфизм f так, что и. Если, то.

2. Пусть f – гомоморфизм, для которого и. Тогдаи.