Алфавит, слова, операции над словами

Пусть V={v₁, v₂,…,v_n}, n³1 – некоторый алфавит. Тогда любая последовательность x₁x₂…x_k, k³0, где x_iÎ V – 1 £ i £k, слово в алфавите V, при k=0 –получается пустое слово, обозначим его l. Множество всех слов алфавита V обозначается V*.

Слово X =x₁…x_k графически совпадает со словом Y=y₁…y_l, если x_iÎV (1 £ i £k), y_jÎV (1 £ j £k), l=k, и для любого i,1 £ i £k, x_i=y_i. Будем обозначать графическое совпадение слов X=Y.

Длиной слова Х (обозначается ïХï) будем называть число вхождений символов в слово Х. Если X =x₁…x_k, то ïХï=k. ïlï=0

Конкатенацией слов X =x₁…x_kи Y=y₁…y_lназывается слово Z= XY= x₁…x_k y₁…y_l. Например, конкатенацией слов «авто» и «бус» будет слово «автобус».

Свойства конкатенации:

l является единицей для конкатенации, т.е. для любого слова Х верно, что Хl=lХ=Х.

Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).

Операция конкатенации не является коммутативной, XY¹YX.

Для конкатенации, как и для произведения, конкатенация n одинаковых слов X обозначается Xⁿ. Считаем, что

X⁰=l для любого слова Х. Множество V* всех слов алфавита V является полугруппой относительно операции конкатенации.

Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.

Если слово Х=Х₁ Х₂, то Х₁ начало слова Х, а Х₂ – конец слова Х.

Говорят, что слово P входит в слово Q, если существует пара слов R и S, такая, что R – первый элемент пары, S – второй элемент пары, и Q =R P S.

Легко доказать

Утверждение: Если слово P входит в слово Q, то существует некоторое слово U, такое, что P – начало U, а U - конец Q.

Следствие: Если слово P входит в слово Q, то P есть начало некоторого конца Q (или конец некоторого начала Q).

Если P есть некоторое начало (конец) Q и P ¹ Q, то P собственное начало (конец) Q.

Конкретные вхождения слова P в слово Q обозначаются R*P*S, где R, P,S – слова в алфавите V, *ÏV. Тогда R – левое крыло вхождения, S – правое крыло вхождения, P - основа.

Говорят, что вхождение P₁ слова P в слово Q предшествует вхождению P₂ слова P в это же слово, если левое крыло вхождения P₁ является собственным началом левого крыла вхождения P₂.

2. Языки. Операции над языками

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

Перечислением элементов.

Ограничивающим свойством.

Через известные множества

Порождающей процедурой.

В основном будем использовать 4 способ, но начнем с третьего.

Например, для любого V множество слов четной длины является языком. Множество слов нечетной длины также является языком, но в отличие от первого — не замкнутым относительно операции конкатенации. Будем обозначать языки буквой L (с индексами или без них). Рассмотрим операции над языками.

Т.к. язык является множеством, то применимы все соответствующие операции, для которых выполняются все законы теории множеств.

В частности, " L, ÆÎ L.

Теоретико-множественные операции

Пусть L₁ и L₂ - два языка над алфавитом V. Язык L называется объединением этих языков (L = L₁È L₂), если L ={x / xÎ L₁Ú xÎ L₂}.

Пересечением языков L₁ и L₂ называется язык L (L = L₁Ç L₂), если L ={x / xÎ L₁& xÎ L₂}.

Дополнением языка L₁ до V* называется язык L (L=V*\L₁), если L={ x/ xÎV* & xÏ L₁}.

Специфические операции

Произведением (иначе конкатенацией) языков L₁ и L₂ называется язык L (L=L₁L₂), если L={x y/xÎL₁ & yÎL₂}.

Например, L₁={ ac, a }, L₂={ cb, b}, тогда L₁L₂={ acb, accb, ab}.

Свойства операции конкатенации:

Операция умножения языков ассоциативна:

L₁ (L₂ L₃)= (L₁ L₂) L₃

Операция умножения языков дистрибутивна относительно объединения

L (L₁ÈL₂) = LL₁È LL₂.

(L₁ÈL₂) L = L₁L È L₂L

Операция умножения языков не коммутативна: L₁ L₂ ¹L₂ L₁.

l L {l}= {l} L = L

Однако L(L₁ÇL₂) Í LL₁Ç LL ₂, в общем случае равенства нет, что легко показать, подобрав соответствующий пример.

В силу ассоциативности операции произведения, как и в случае конкатенации цепочек,

записывается как L=L₁ⁿ. По определению L⁰={l}. Отметим, что {l} ¹ Æ. так как Æ (пустой язык) вообще не содержит никаких цепочек.

Итерацией языка L₁ называется язык L(L=L₁*), если

. Как нетрудно видеть, итерация алфавита V* (алфавит можно рассматривать как язык, состоящий из односимвольных слов) образует язык, состоящий из всех возможных цепочек, составленных из символов V. Это обстоятельство и объясняет, почему V* используется для обозначения всех слов над алфавитом V.