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

Введение

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

Бесконечная последовательность букв алфавита А называется сверхсловом, - сверхслово из бесконечного числа букв а. Пустым называется слово, не содержащее ни одной буквы. Оно обозначается через e. Очевидно, |e|=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 относительно алфавита А. И если e всегда включено в А*, то язык может как содержать e, так и не содержать его. В последнем случае .

Пусть , . Тогда язык называется конкатенацией (сцеплением, произведением) языков и . При этом , (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 – гомоморфизм, для которого и . Тогда и .