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