ТФЯ - 1. Основные определения

Немного еще теории перед конкретикой Лиспа и Хаскеля, математическая теория языков вообще (как языков людей, так и языков роботов).

Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами).

Словом в алфавите А называется конечная последовательность элементов А.

Слово, не содержащее ни одного символа, называется пустым словом.

Множество всех слов в алфавите А обозначается А*.

Если С входит в А*, то С называется формальным языком над алфавитом А.

Язык А* - С называется дополнением языка С относительно алфавита А.

Если x и y - слова в алфавите А, то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией, (катенацией, сцеплением) слов x и y. Иногда конкатенацию слов x и y обозначают x * y.

Слово в какой-то степени - это повтор его столько раз, сколько в степени.

Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.

Через |w|a обозначается количество вхождений символа a в слово w.

Итерацией языка языка L (обозначение L*) называется язык, состоящий из всех степеней данного языка.

Обращением или зеркальным образом слова w (обозначается w^R) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.

Говорят, что слово x - префикс (начало) слова y, если y = xu для некоторого слова u.

Через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L.

Слово x - суффикс (конец) слова y, если y = ux для некоторого слова u.

Через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L

Слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v

Через Subw(L) обозначается множество, состоящее из всех подслов слов языка L.

Слово a1a2...an (длины n >= 0) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u0, u1, ..., un, что u0a1u1a2...anun = y.

Через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей языка L.