Гладкий - Формальные грамматики и языки - 1973 (947381), страница 4
Текст из файла (страница 4)
Наибольшее значение высоты узла дерева (совпадающее, очевидно, с наибольшим значением ранга н с ран- б) Этот термин обычен я лингякстических работах и часто ястречается з работах пп математической лингвистике. В теп[>ия графов более принят термин вершина; мы избегаем егп потому, ято яп. мнагих мзтематико-линсзистических работах «зершиной Лереня» 'няЕыяявт корень (см, ниже), том корня) называется высотой дерева.
Наибольшее значение степени узла дерева называется степенью дерева. Дерево, состоящее из одного лишь корня, называется е д и н и ч н ы м. Множество М с заданными на нем двумя бинарными отношениями >с[ и Ря называется 6 и графом (и обозначается (М; >сь»сз)). Нагруженным биграфом называется упорядоченная система (М; )сь >ся, с>, й), где (М; Р[, бся) — биграф, (> — конечное множество и д — отображение М в сб'. Упорядоченная система (М; )с, бр), где М и )с — множества и б[б — отображение )с в множество всевозможных упорядоченных пар элементов М, называется мульт н г р а ф о м. Элементы М называются у з л а м и мультиграфа, элементы )с — его дугами.
Если (а, Ь)= = ся(а), говорим, что дуга а идет нз а в Ь; а есть н ач а л о сх; Ь есть к о н е ц и. П у т ь в мультиграфе определяется так же, как в графе. (Граф можно было бы определить как мультиграф с равнозначным бр.) й 1.1. Цепочки и языки Мы будем рассматривать непустое конечное множество )г, которое будем называть словарем (или алфавитом), а его элементы — элементарными символ а ми (нли просто символами, а также букв а м и). Произвольную конечную последовательность элементов )б, т.
е. отображение в Р некоторого (конечного) начального отрезка натурального ряда, будем называть цепочкой *) в словаре )г. Отображаемый отрезок натурального ряда может быть и пустым; тогда мы говорим о п у с т о й ц е п о ч к е. Непустую цепочку мы, как правило, будем записывать в виде ш = Ь, ... Ь„, где Ь, — образ числа й Пустую цепочку будем обозначать символом Л. Мощность отображаемого отрезка натурального ряда будет называться д л и н о й цепочки; н частности, длина пустой цепочки равна нулнх Длина б [ )М, у б йзботзх те[>минем с л и и о яо избежзнне ненужной омонимин я лингиистияеских приложениях.
ЦЕПОЧКИ И ЯЗЫКИ «1.1! ОСНОВНЫЕ ПОНЯТИЯ [гл. Н апример, алкилолкоксисилин — цепочка длины 1 в словаре У, состоящем из 32 русских букв, а такж в словаре У' = (а, и, к, л, и, о, с) и в любом словаре ое и ,сд ржащем У. Иногда мы будем изображать цепочку Рис. 1. Ь , ... Ь„на отрезке горизонтальной прямой так, как по казано на рис. 1. М ножество всех цепочек в словаре У будет обозна-' чаться через У*, множество всех непустых цепочек в У вЂ” через У'. Конкатенацией (или результатом конкатенации) непУстых цепочек Ь, ... Ь„и с~ ... ср назь[ваетсЯ це-' почка д~ ...
с[„„.р, где А = Ьь ..., с(„= Ь, = сь .. с[,+р — — ср. Кроме того, конкатенация цейочек в и Л, равно как и Л и в, где в — произвольная цепочка, считается по определению равной в. Конкатенацию цепочек в и ч~ мы будем обозначать втр, 3 аметим, что слово «конкатенация» обозначает у нас и операцию и ее результат. Иногда эту операцию называют также умножением, а ее результат — произв еде н и ем цепочек.
О перация конкатенации, очевидно, ассоциативна, но не коммутативна *). Вместо вв ... в мы будем обычно писать в"; в' п риз будет означать в; во будет означать Л. Если в = сутр, мы будем называть [[т началом в н тр концом в. В частности, всякая цепочка есть начало и конец самой себя. М ы введем также две частичные операции, обратные для конкатенации: левое деление и пр авое деление. Именно, левым (правым) частным от делен ия цепочки в на цепочку в называется цепочка тр такая, что [ртр = в (соответственно ~мр = в). Левое частное от деления в на [р будет обозначаться через тр'~в, правое — через в "[р. 1 За исключением случая, когда У состоит из одиого»лемеита.
Например, цепочка рококо есть конкатенация цепочек рок и око, цепочка окорок — конкатенация цепочек око и рок; рок=око';окорок=рококо,"око; око=рок', ',рококо=окорок(рок; частных рок',окорок, око", ",рококо, окорок 'око, рококо,г'рок не существует. Если для каких-либо цепочек в, ~р, т[ь т[т в словаре У имеет место равенство в = т[1[рт[т, мы будем называть цепочку т[~ е Ч1ет[е, где символ е не принадлежит вхождением цепочки тр в цепочку в. Если существует вхождение ~р в в, мы будем называть [р подцеп ч к о й в. В случае, когда длнна цепочки тр равна 1, т. е.
[р состоит из одного символа Ь, будем говорить о вхождении си м вол а Ь в цепочку в. Вхождения символов в цепочку мы нередко будем называть ее т о чк а м.и. Число вхождений символа а в цепочку в будет обозначаться (в[«. Если а = т[1»Ьет[т и б = $[есе$1 — точки одной и той же цепочки в = т[,Ьт[т = $,с$ь и если при этом (т[,) ()$~), мы будем писать а ( б или р ) а и говорить, что а л е ж н т (или р а с п о л о ж е н а) л е в е е б, а б — правее а. Если а < Р ( у или у < б < а, говорим, что б лежит (илн р а с и о л о ж е н а) м ежду а и у.
Для любых двух точек а, р цепочки в таких, что а < р, мы будем называть множество точек $, удовлетворяющих неравенствам а - 5 ( б, о т р е з к о м ц еп о ч к и в и обозначать [а, р), а множество точек, удовлетворяющих неравенствам а ( $ ( б, — и н т е р в алом цепочки в и обозначать (а, р). Иногда нам будут нужны также несобственные интервалы ( —, а) и (а, — ) — множества точек, удовлетворяющих соответственно неравенствам $ ( а и а ( 5.
Интервал, в отличие от отрезка, может быть пуст. Между отрезками цепочки и вхождениями в нее непустых подцепочек имеется очевидное взаимно однозначное соответствие. Иногда для упрощения изложения отрезки будут отождествляться с соответствующими подцепочками (только в тех случаях, когда это не ведет к недоразумениям). Пары точек а, р и у, Ь, по определению, разделяют друг друга, если одна нз точек у, Ь лежит, а другая не лежит между а н Р (или, что то же самое, ОСНОВНЫЕ ПОНЯТИЯ [гл. г ЦЕПОЧКИ И,ЯЗЫКИ одна из точек а, р лежит, а другая не лежит между у, и б).
Пример. Цепочка рококо содержит два вхождения. цепочки око; р око«ко и рок«око«, одно вхождение символа Ел «р» ококо, 7 вхождений пустой цепочки: ««рококо, р ««ококо и т. д. Если обозначить вхождения символа о (слева направо) через а, р, у, то а «,. р ( у; отрезкам [а, р] и [р, у] отвечают разные вхождения одной и той же подцепочки око. Иногда мы будем фиксировать некоторый пересчет- словаря У! а1, ..., а„и связывать с этим пересчетом ., следующее отношение «предшествования» на У": более короткая цепочка предшествует более длинной, а для цепочек равной длины предшествование определяется лексикографически (т.
е. цепочка а, ... а! а,' ... а, ! «-! «« предшествует цепочке а, ... а, а,.... а1, если !',<1,~. 1 «-! !! ~« Это отношение является линейным порядком; более того, существует взаимно однозначное отображение тл . У« — "'» М (Л' = (О, 0...)), сохраняющее порядок (упраж-, нение !.3). Число ч(!З) мы будем называть с та нда р тн ы м н о м е р о м цепочки !э, а определенное только что отношение на У' — стандартным порядком. Произвольное множество цепочек в словаре У мы будем называть языком в этом словаре. Рассматривается, в частности, и пустой язык; обозначаться он будет, в согласии с $1.0, символом 8. Над языками можно производить обычные теоретико- множественные операции — о б ъ е д и н е н и е (обозначается О), пересечение (обозиачается ()), вы читан и е (обозначается — ), взятие до п о л н е н и я (дополнение языка Е до множества У« будет обозначаться через СКЕ илн, если недоразумение невозможно, через СЕ; дополнениедо множества У+ — соответственно через СКЕ или С Е).
Введем теперь некоторые специфические операции над языками, Умножение (иначе, прямое умножение или конкатенация) определяется как операция, ставящая в соответствие двум языкам Е! и Еэ язык Е = (!р!Р[ф ен Е„!Р ~ ЕЗ]. Этот язык обозначается ЕЕ, и называется (прямым) произведением на Ез (или конкатенацией Е! и Ег) Для экономии скобок мы будем считать, что умножение связывает теснее, чем объединение, так что, например, 1.! 0 ЕЗЕ! будет означать Е! 0 (Е|Е!).
Операция умножения ассоциативна, но не коммутативна. Ввиду ее ассоциативности ясен смысл записи. Е, ... 1.„. Кроме того, она дистрибутивна относительно объединения: 1,(1! 0 Ез) = ЕЕ! 0 ЕЕа', (1!0Ег)Е = = Е,Е 0 Е»Е (упражнение 1А, а) ).
И т е р а ц н е й (или результатом итерации) языка называется язык Ц Е", где Е' = (Л), Е! = Е и прн п ) 1. Этот язык обозначается Е» — 1 л р«! Е". Иногда нам будет удобно рассматривать также усеченную итерацию языка Е, определяемую как Д Е"; она будет обозначаться Е+. » 1 Операции левого и правого деления языка' иа цепочку определяются и обозначаются соответственно следующим образом: !»" Е = (1р [еф ~ Ц; 1. ~'!э = (ф ) фа ен Ц. Наконец, подстановка языков Е!...,, Е в язык Е вместо символов а1, ..., а„есть операция, сопоставляющая языку Е в словаре У = (а1, ..., а„) н языкам Е„..., 1, в словарях У1, ..., У„соответственно следующий язык в словаре У! 0...
0 У,: [!»1, ... оз! !а1, ... а!«~Е, о1, ееЕ!и ..., !э! ЕеЕ! '] 01' где Е'=(Л), если Л ее 1„и Е' = 8, если Л Ф 1.. Этот язык будетобозначаться 5(Е; аь ..., а„[ЕП ..., 1.„). В частном случае, когда языки Е1, ..., Е„одноэлементны, подстановка называется гомом орфи ым отображением ем, или гом ом орфизмом, языка Е. Если 1- — язык в словаре У = (аь ..., а„) и 11 «: — У, то го! моморфное отображение 5(Е; аь ..., О„[Е1, ..., Е„), где Е! есть (а!) при а! Ен Е! и (Л) при а! ф ЕЕ называет-- ся проектированием Е иа (1, а его результат— ОСНОВные НОнятия !ГЛ.
! прае кци ей 1. на У. Образ цепочки при проектировании также называется ее п р о е к ц и ей. Проекцию цепочки со и языка !. на словарь (У мы будем обозначать соответственно Просп и Прей. Если (со) — язык, состоящий из одной цепочки ы, то . мы будем вместо Цео), (ы)1., (ы)* и (ы)' писать соответственно Ьы, сп1„ы" н о'. всев Пример. Если У= (0,1), Ь вЂ” язык, состаящ " озможных двоичных записей целых положительных чисел (т.
е. цепочек, начинающихся символ !), ык, состоящий из всевозможных двоичных записей нечетных положительных чисел (т. е. цепочек, начинаю- шихся и оканчивающихся символом !), то 1. = 1У", Ц,=(1) и!У 1, -,=. =.,-(!)' "...==.'И ( ' *); ' =; ы';В = У, если ы начинается единицей; ы'Х = 8, если оь начинается нулем; Ь,~'в= = (.,ЩЛ), если оз оканчивается единицей; 1.~г'о = 8 если со оканчивается нулем; 5(1.; О, !',Ь, Ь) = В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
