Под алфавитом å будем понимать непустое конечное множество символов.
Цепочка, или строка – это последовательность символов некоторого алфавита, при этом символы в строке могут повторяться. Для цепочки важен ее состав, порядок символов и их количество.
Над цепочками можно выделить следующие операции:
Конкатенацией, или сцеплением (сложением) цепочек, называется строка, полученная их объединением. Свойства: Так как в цепочке важен порядок символов, очевидно, что операция сложения не коммутативна. Конкатенация ассоциативна, т.е. "a,b,g (ab)g = a(bg).
Обращение цепочки x – это запись ее символов в обратном порядке, обозначается xR. Свойство операции обращения: "a,b (ab)R= bRaR.
Итерация цепочки n раз – это ее сцепление (повторение) n раз, обозначается an.
Если å – некоторый алфавит, то:
å+ – множество всех цепочек над алфавитом å без l.
å* – множество всех цепочек над алфавитом å, включая l.
Языком L над алфавитом Σ называют произвольное множество цепочек из символов этого алфавита. Такой язык принято обозначать L(Σ).
Для любого языка L(Σ) справедливо L(Σ) Í Σ*.
Язык L(Σ) включает в себя язык L¢(Σ): L¢(Σ) Í L(Σ), если "aÎL¢(Σ) aÎL(Σ).
Два языка совпадают (эквивалентны): L¢(Σ) = L(Σ), если L¢(Σ) Í L(Σ) и L(Σ) Í L¢(Σ).
Конкатенацией (объединением) языков L1 и L2 называют язык L, состоящий из всевозможных сцеплений цепочек языков L1 и L2: L = L1·L2 =
