Структуры данных и модели вычислений

         

Основные понятия и обозначения


Алфавит — конечное множество абстрактных символов, как правило, упорядоченное в так называемом алфавитном порядке.

Слово (в алфавите ) — конечная последовательность символов (алфавита).

Длина слова— количество вхождений символов в слово. Длина слова , обычно обозначается .

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

Слово длины () можно отождествить с элементом декартова произведения (, в котором

сомножителей, обозначаемого . При

имеем , состоящее из одного пустого слова; не путать с пустым множеством, обозначаемым знаком .

Замечание.

При отождествлении элемента декартова произведения со словом полагаем, что слово составлено из входящих в него символов в соответствующем порядке.

Множество всех слов в алфавите обозначают

Множество всех непустых слов в алфавите обозначают

Сверхслово (в алфавите ) — бесконечная последовательность символов (алфавита ).

Формальный язык (в алфавите ) — множество слов (в алфавите ).

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

Начальный фрагмент слова , имеющий длину , называется префиксом длины

слова , обозначается .

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

Если , то префикс и суффикс называются собственными. Заметим, что при нашем определении пустое слово

будет и собственным префиксом, и собственным суффиксом любого слова .

Операции над формальными языками. Поскольку формальные языки являются множествами, то к ним применяются обычные теоретико-множественные операции: объединение, пересечение, дополнение (до множества всех слов в рассматриваемом алфавите). Кроме перечисленных, применяются специфические операции — это конкатенация двух языков и итерация языка.

Результатом конкатенации языков и

является язык , обозначаемый также . Результат конкатенации

экземпляров языка обозначим через .

Результатом итерации языка является язык . Заметим, что

и поэтому при любом .

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

Основные тождества. Пусть , , — произвольные формальные языки над некоторым фиксированным алфавитом, тогда справедливы следующие тождества:



Содержание    Вперед