Структуры данных и модели вычислений
Основные понятия и обозначения
Алфавит — конечное множество абстрактных символов, как правило, упорядоченное в так называемом алфавитном порядке.
Слово (в алфавите ) — конечная последовательность символов (алфавита).
Длина слова— количество вхождений символов в слово. Длина слова , обычно обозначается .
Пустое слово — пустая последовательность, то есть последовательность, не содержащая ни одного символа. Пустое слово, соблюдая традиции, часто обозначают греческой буквой , полагая при этом, что она не является символом рассматриваемого алфавита.
Слово длины () можно отождествить с элементом декартова произведения (, в котором
сомножителей, обозначаемого . При
имеем , состоящее из одного пустого слова; не путать с пустым множеством, обозначаемым знаком .
Замечание.
При отождествлении элемента декартова произведения со словом полагаем, что слово составлено из входящих в него символов в соответствующем порядке.
Множество всех слов в алфавите обозначают
Множество всех непустых слов в алфавите обозначают
Сверхслово (в алфавите ) — бесконечная последовательность символов (алфавита ).
Формальный язык (в алфавите ) — множество слов (в алфавите ).
Конкатенация слов— двухместная операция над словами, заключающаяся в приписывании второго слова к первому. Результат конкатенации слов и обозначается .
Начальный фрагмент слова , имеющий длину , называется префиксом длины
слова , обозначается .
Конечный фрагмент слова , имеющий длину , называется суффиксом длины слова , обозначается .
Если , то префикс и суффикс называются собственными. Заметим, что при нашем определении пустое слово
будет и собственным префиксом, и собственным суффиксом любого слова .
Операции над формальными языками. Поскольку формальные языки являются множествами, то к ним применяются обычные теоретико-множественные операции: объединение, пересечение, дополнение (до множества всех слов в рассматриваемом алфавите). Кроме перечисленных, применяются специфические операции — это конкатенация двух языков и итерация языка.
Результатом конкатенации языков и
является язык , обозначаемый также . Результат конкатенации
экземпляров языка обозначим через .
Результатом итерации языка является язык . Заметим, что
и поэтому при любом .
Замечание. При работе с формальными языками операцию объединения часто обозначают знаком "". В следующих тождествах используется именно это соглашение.
Основные тождества. Пусть , , — произвольные формальные языки над некоторым фиксированным алфавитом, тогда справедливы следующие тождества:
