1. Повторения

1.1. Слова и языки

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

Алфавит ∑ - это конечное непустое множество. Буквы (символы) - элементы алфавита ∑. Слово над алфавитом ∑ - это конечная цепочка, состоящая из нуля или более букв из ∑, причем одна и та же буква может входить в слово несколько раз. Цепочка, состоящая из нулевого количества букв, называется пустым словом и обозначается λ. Таким образом λ, 0, 1, 010, 1111 суть слова над алфавитом ∑ = {0, 1}. Множество всех слов (соответственно всех непустых слов) над алфавитом ∑ обозначается ∑* (соответственно ∑+). Множество ∑* бесконечно для любого ∑. С алгебраической точки зрения ∑* и ∑+ представляют собой свободный моноид и свободную полугруппу с множеством образующих ∑.

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

Если x и y - слова над алфавитом ∑, то их катенация xy (результат приписывания) - тоже слово над ∑. Катенация является ассоциативной операцией, и пустое слово служит единицей по отношению к ней: xλ = λx = x для всех x. Если x - слово, а i - натуральное число, то xⁱ обозначает слово, полученное катенацией i слов, каждое из которых есть x. По определению x⁰ - пустое слово λ.

Длина слова x, обозначаемая |x|, есть число букв в x, причем каждая буква считается столько раз, сколько раз она входит в x. Опять же по определению |λ| = 0. Функция длины обладает некоторыми формальными свойствами логарифма: для всех слов x, y и неотрицательных целых i

Слово x называется подсловом слова y, если существуют такие слова x₁ и x₂, что y = x₁xx₂. Если при этом x₁ = λ (соответственно x₂ = λ), то x называется началом или префиксом (соответственно концом или суффиксом) слова y.

О подмножествах множества ∑* говорят как о (формальных) языках над ∑. Таким образом,

являются языками над алфавитом ∑ = {a, b}, причем первый конечен, а второй бесконечен. Конечный язык может быть, хотя бы теоретически, задан списком всех его слов. Подобная процедура для бесконечных языков невозможна - для их задания необходимо какое-то описание, отличное от списка. Финитными заданиями бесконечных языков в основном и занимается теория формальных языков. Различные классы финитно задаваемых языков будут рассмотрены ниже.

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

В теории языков важнейшей операцией является операция морфизма. Морфизмом называется отображение h: ∑*→Δ*, где ∑ и Δ - алфавиты, удовлетворяющее условию

Для языков L над ∑ определим h(L) = {h(w)|w∈L}. (С алгебраической точки зрения морфизм языков есть моноидный морфизм, естественным образом продолженный на подмножества моноидов.) В силу (1.1) для задания морфизма h достаточно указать все слова h(a), где а пробегает все элементы конечного алфавита ∑.

Тройка G = (∑, h, w), где ∑ - алфавит, h: ∑*→∑* - морфизм и w - слово над ∑, называется DOL-системой. DOL-система G определяет последовательность S(G) слов над ∑:

а также язык L(G) = {h¹(w)|i≥0}. Таким образом, DOL-система является очень простым средством задания языка. Языки, заданные с помощью DOL-системы, называются DOL-языками. Они рассматриваются в гл. 5; там же объясняется сокращение DOL.

Бесконечная последовательность элементов алфавита ∑ называется ω-словом или сверхсловом. Таким образом, ω-слово может быть отождествлено с отображением множества неотрицательных целых чисел в ∑. Очень удобным средством задания конкретных ω-слов являются DOL-системы. Именно, рассмотрим DOL-систему G = (∑, h, w), такую, что

т. е. w - собственное начало (начало слова, не совпадающее с самим словом) слова h(w) и, кроме того, h является нестирающим (т. е. h(a)≠λ для всех a из ∑). Тогда, согласно (1.2),

и вообще

Равенство (1.3) показывает, что hⁱ(w) для всех i является собственным началом слова hⁱ⁺¹(w). (При этом hⁱ(x)≠λ, так как h нестирающее.) Следовательно, ω-слово α может быть определено как "предел" последовательности hⁱ(w), i = 0, 1,2 ... . Точнее, α представляет собой ω-слово, начало которого, имеющее длину |hⁱ(w)|, есть hⁱ(w), i = 0, 1,2, ... . (Понятия начала и подслова естественным образом распространяются и на ω-слова. Слово x является подсловом ω-слова α, если α можно записать в виде x₁xα₁, где α₁ и x₁ - слово и ω-слово соответственно. Если x₁ = λ, то x называется началом ω-слова α.) О полученном таким образом ω-слове α говорят, что оно порождено DOL-системой G.