Цепочки символов. Операции над цепочками символов

Языки и грамматики

Языки и цепочки символов. Способы задания языков

Цепочкой символов (или строкой) называют произвольную последовательность символов, записанных один за другим. Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении.

Далее цепочки символов будем обозначать греческими буквами: а, (3, у.

Итак, цепочка — это последовательность, в которую могут входить любые допус­тимые символы. Строка, которую вы сейчас читаете, является примером цепочки, допустимые символы в которой — строчные и заглавные русские буквы, знаки препинания и символ пробела. Но цепочка — это необязательно некоторая ос­мысленная последовательность символов. Последовательность «аввв.магрьь,.лл» — тоже пример цепочки символов.

Для цепочки символов важен состав и количество символов в ней, а также поря­док символов в цепочке. Один и тот же символ может произвольное число раз ходить в цепочку. Поэтому цепочки «а» и «аа», а также «аб» и «бя» — это раз-ичные цепочки символов. Цепочки символов аир равны (совпадают), а = р, ₀°^{Ли они} имеют один и тот же состав символов, одно и то же их количество и

^инаковый порядок следования символов в цепочке, "к*

личество символов в цепочке называют длиной цепочкжДлнна цепочки сим-^л°в а обозначается как |а|. Очевидно, что если а - р, то и~|а| = |р|.

(ofi ^9ВНо^ ^операцией над цепочками символов является операция конкатенации ^ЪеДинения или сложения) цепочек.

348 Глава 9. Формальные языки и

Конкатенация (сложение, объединение) двух цепочек символов — это допи вание второй цепочки в конец первой. Конкатенация цепочек аир обознач ся как ар. Выполнить конкатенацию цепочек просто: например, если а ^: а Р = «ег», то ар = «с

Так как в цепочке важен порядок символов, то очевидно, что операция конка нации не обладает свойством коммутативности, то есть в общем счучае 3 a r такие, что аР^Ра. Также очевидно, что конкатенация обладает свойством ас циативности, то есть (сф)у = а(Ру).

Можно выделить еще две операции над цепочками.

Обращение цепочки — это запись символов цепочки в обратном порядке. Обра­щение цепочки а обозначается как a^R. Если a = «абвг», то a^R = «гвба». Для опе­рации обращения справедливо следующее равенство V a,p: (aP)^R = p^Ra^R.

Итерация (повторение) цепочки п раз, где neN, n > 0 — это конкатенация це­почки самой с собой п раз. Итерация цепочки a n раз обозначается как а^п. Для операции повторения справедливы следующие равенства V а: а¹ = а, а² = аа а³ = ааа,... и т. д.

Среди всех цепочек символов выделяется одна особенная — пустая цепочка. Пустая цепочка символов — это цепочка, не содержащая ни одного символа. Пустую цепочку здесь везде будем обозначать греческой буквой X (в литературе ее иногда обозначают латинской буквой е или греческой s).

Для пустой цепочки справедливы следующие равенства:

1. N = 0;

2. Va: Ха = аХ = a;

3. №-\;

4. Vn>0: Xⁿ = X;

5. Va: a⁰ - X.

Дата добавления: 2015-06-27