Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
той же цепочки со = = ЪСЪ, и если при этом
|Г)1 J < lii |, мы будем писать а<р или Р>а и говорить, что а лежит (или расположена) левее р, а р — правее а. Если а < р < y или y < Р < «. говорим, что р лежит (или расположена) между а и y- Для любых двух точек а, Р цепочки со таких, что а ^ р, мы будем называть множество точек удовлетворяющих неравенствам a^i^p, отрезком цепочки со и обозначать [а, р], а множество точек, удовлетворяющих неравенствам a < g < р,— интервалом цепочки со и обозначать (а, р). Иногда нам будут нужны также несобственные интервалы (—, а) и (а, —) — множества точек, удовлетворяющих соответственно неравенствам | < а и a < ?. Интервал, в отличие от отрезка, может быть пуст. Между отрезками цепочки и вхождениями в нее непустых подцепочек имеется очевидное взаимно однозначное соответствие. Иногда для упрощения изложения отрезки будут отождествляться с соответствующими подцепочками (только в тех случаях, когда это не ведет к недоразумениям).
Пары точек а, р и y, б, по определению, разделяют друг друга, если одна из точек y> 6 лежит, а другая не лежит между аир (или, что то же самое,
22
ОСНОВНЫЕ понятия
[ГЛ.’ I
одна из точек а, р лежит, а другая не лежит между у, и б).
Пример. Цепочка рококо содержит два вхождения -цепочки око: р * око * ко и /?о/с * око «, одно вхождение символа р\ *р*ококо, 7 вхождений пустой цепочки:
* * рококо, р * * ококо и т. д. Если обозначить вхожде-: ния символа о (слева направо) через а, р, у, то а < < р < YI отрезкам [а, |3] и [р, у] отвечают разные вхождения одной и той же подцепочки око.
Иногда мы будем фиксировать некоторый пересчет-словаря V: аи ..., ah и связывать с этим пересчетом 5 следующее отношение «предшествования» на V*: более короткая цепочка предшествует более длинной, а для : цепочек равной длины предшествование определяется лексикографически (т. е. цепочка а, ... а, а, ... а,
*1 *5-1 lS П
предшествует цепочке а{ ... ai ^aj ... а;. , если
Это отношение является линейным порядком; более г того, существует взаимно однозначное отображение v: . у* дг (N = {0,1,...}), сохраняющее порядок (упраж- «
нение 1.3). Число v(a>) мы будем называть стандартным номером цепочки со, а определенное только что отношение на V* — стандартным порядком.
Произвольное множество цепочек в словаре V мы будем называть языком в этом словаре. Рассматривается, в частности, и пустой язык; обозначаться он будет, в согласии с § 1.0, символом 0.
Над языками можно производить обычные теоретикомножественные операции — объединение (обозначается U), пересечение (обозначается П), вычитание (обозначается —), взятие дополнения (дополнение языка L до множества V* будет обозначаться через CyL или, если недоразумение невозможно, через CL; дополнение до множества V? — соответственно через CvL или С L).
Введем теперь некоторые специфические операции над языками. Умножение (иначе, прямое умножение или конкатенация) определяется как операция, ставящая в соответствие двум языкам L] и L% язык L = {фг|51 ср е Lu ipeL2}. Этот язык обозначается LiLz и называется (прямым) произведением Li
ЦЕПОЧКИ и .языки
23.
на L2 (или конкатенацией Li и L2). Для экономии скобок мы будем считать, что умножение связывает теснее, чем объединение, так что, например, Li U L2L3 будет означать Li U (L2LS).
Операция умножения ассоциативна, но не коммутативна. Ввиду ее ассоциативности ясен смысл записи, Li ... Ln. Кроме того, она дистрибутивна относительно объединения: L(Li U Lz) = LLi U LL2, (L\[)L2)L —
= LiL (J L2L (упражнение 1.4, a)).
Итерацией (или результатом итерации) языка
ОО
L называется язык (J Ln, где L° = {Л}, L1 = L и
п=0
Ln = L...L при п> 1. Этот язык обозначается
п раз
L*. Иногда нам будет удобно рассматривать также усеченную итерацию языка L, определяемую как
оо
(J Ln; она будет обозначаться Z.+.
/2=1
Операции левого и правого деления языка' на цепочку определяются и обозначаются соответственно следующим образом:
cd\Z. = {ф | соф е L}; L/со = {ф | ф<» е L}.
Наконец, подстановка языков Lu Ln в язык L вместо символов ait ..., ап есть операция, сопоставляющая языку L в словаре V = {аь ..., ап} и языкам Lit ..., Ln в словарях Vi, ..., Vn соответственно следующий язык в словаре Vi U ... U Vn-
{ш^ ... I ai{ ... L, ..., (&ik e (J L',
где L' = {A}, если AeL, и L'= 0, если Л ф L. Этот язык будет обозначаться S(L; аи ..., a„\Li, ..., Ln). В частном случае, когда языки Lu ..., /.„ одноэлементны, подстановка называется гомоморфным отображением, или гомоморфизмом, языка L. Если L ~ язык в словаре V — {ait ..., а„} и U ^ V, то гомоморфное отображение S(L; а\.........an\L[......L'n),
где L'i есть {а{} при е (У и {Л} при а, ф U, называемся проектированием L Ш V, ъ его результат —
й4
ОСНОВНЫЕ понятия
[ГЛ. I
проекцией L на U. Образ цепочки при проектировании также называется ее проекцией. Проекцию цепочки со и языка L на словарь U мы будем обозначать соответственно При© и При^-
Если {со} — язык, состоящий из одной цепочки и, то мы будем вместо L{a>}, {(o}L, {со}* и {со}+ писать соответственно Leo, соL, и* и м+.
