XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 77
Текст из файла (страница 77)
Говоря неформально, описанное преобразование грамматики состоит в переобозначении ее нетерминэлов таким образом, что вместо каждого нетерминала ставится его „двойник", причем „двойники", соответствующие разным нетермнналам, различны. 486 Х КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ 7.3. Классификация грамматик и языков Напомним, что единственное ограничение, накладываемое на правило вывода любой грамматики, состоит в том, что в левую частпь правила должен входить хотя бы один нептерминвд. В зависимости от дополнительных ограничений, накладываемых на правила вывода граммвтпини, различают следующие основные классы грамматик.
1. Грамматпики таина О, или грамматпики оби4его вида. Здесь на правила вывода не накладывается никаких дополнительных ограничений. 2. Неукорачиватои4ие грамматпики. Каждое правило такой грамматики имеет вид а -+ р, где ~ст~ < ф.
Таким образом, длина правой части правила не меньше длины левой. Грамматика С4 из примера 7.5 есть неукорачивающая грамматика, но грамматика Сз из того же примера таковой не является. 3. Контпекстпнооависимые грамматпики (КЗ-грамматпики). Грамматику называют контекстно. зависимой грамматикой (КЗ-грамматикой), если любое ее правило вывода имеет вид уф ~ у05, где А — нетпермина ц, с — некоторая цепочка, С -,4 Л. Каждое такое правило, называемое КЗ-правилом, позволяет заменить нетерминзл А в „контексте, образуемом цепочками у и тР в обьединенном влдтввитпе, непустой цепочкой С (см. замечание 7.1). Иногда цепочку у называют левым контпекстпом, а цепочку т4 — правым контпекстпом данного КЗ-правила Из определения видно, что каждая КЗ-грамматика является неукорачивающей.
Грамматика С4 из примера 7.5 не является КЗ-грамматикой, так как правило СВ + ВС не является КЗ-правилом. Остальные же правила вывода этой грамматики — КЗ-правила. Грамматика Сз из примера 7.5 не является КЗ-грамматикой хотя бы из-за наличия правила вывода с пустой правой частью. КЗ-грамматикой является грамматика из примера 7.3. 7.3. Классификация грвннатик я языков 487 Если в КЗ-правиле снять требование непустоты цепочки ~, то получим грамматику, которую называют обобщенной К3-грамматикой (или, коротко, ОКЗ-грамматпиной). 4. Контпекстносвободные граммагпини (КС-граммапдини).
Каждое правило такой грамматики имеет вид А -+ а, т.е. левая часть каждого правила вывода есть нетерминал, а правая — произвольная (может быть и пустая) цепочка в объединенном алфавите. С практической точки зрения это наиболее важный класс грамматик, поскольку именно в терминах КС-грамматик описывается синтаксис языков программирования, и этим грамматикам будет посвюцена отдельная глава. Грамматики Сз, Сз, 04 вэ примера 7.5 являются КС-грамматиками. 5. Линейные граммаднини. Каждое правило такой грамматики имеет вид А -д иВе или А -+ и, т.е.
в правой части правила может содержаться не более одного вхождения нетерминала. Если во всех правилах вида А -+ иВо имеет место е = Л, то грамматика незываетсл праволинейной, а если и = Л— лево линейной. Пример 7.6. Линейной является грамматика Се = ((ад,..., а„), (Я), Я, Ре), где множество правил вывода Ре есть Я -+ ад Бад ~ азБаз ~... а„Ба„~ ад ~ аз ~... а„~ Л. Можно доказать, что эта грамматика порождает все палиндромы в алфавите р, т.е. все цепочки, читаемые слева направо так же, как и справа налево.
Например, для У = д'а, Ь, с) цепочка асЬЬса — палиндром. Вывод его в грамматике Се (для данного терминального алфавита) будет иметь вид Я ~- аЯа 1- асЯса ~ асЬЯЬса 1- асЬЛЬса = асЬЬса. 488 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Замечание 7.2. Формальное определение палиндрома таково. Назовем инверсией непустой цепочка х = х(1)х(2)... х(Й вЂ” 1)х(Й) Е У цепочку х = х(к)х(к-1)...х(2)х(1). Длл пустой цепочки Л по определению считаем Лн = Л. ела« ландром в алфавите У вЂ” это любая цепочка х, для которой и 6.
Рееуллрные граммаепаии. У такой грамматики каждое правило имеет вид А -+ аВ илн А -+ а, где а есть либо терминал, либо пустая цепочка. Регулярные грамматики— частный случай праволинейных грамматик. Эти грамматики подробно будут рассмотрены в 7.4. Приведем без доказательства некоторые утверждения о классах грамматик. Теорема 7.2. 1. Для любой грамматики типа О может быть построена эквиваленщная ей ОКЗ-грамматика.
2. Для любой неукорачивающей грамматики может быть построена эквивалентная ей КЗ-грамматика. 3. Для любой леволннейной грамматики может быть построена эквивалентная ей праволинейнея грамматика, и, наоборот, для любой праволинейной грамматики может быть построена эквивалентная ей леволинейнал грамматика. 4.
Для любой праволинейной грамматики может быть построена эквивалентная ей регулярная грамматика. ф Отметим,что доказательства первых двух пунктов теоремы 7.2 весьма нетривиальны'. Классификация языков, порождаемых грамматиками, тесно связана с классификацией самих грамматик, хотя и не тождественна ей. Язык относят к иласср С, если существу- 'Сеел Гевшкое В.М., Неякмкк Г.Е., Юкеекко Е.Л. 7.3. Клаесифвкацял грамзкагик и лзмкоз 489 ет грамматика класса С, порождающая данный юык. Таким образом опредевпотся языка 1пипа О, неукорвчивающие лэыки, контвексшно.зависимые лзыки (ХЗ-языки), обобщенные конпьекстнооависимые лэыки (ОКЗ-языки), конеекстпно<вободные лзыка (КС-языки), линейные лзыки, право- и леволинебные лзыки, реауллрные лэыки.
Так как всякая ОКЗ-грамматика является грамматикой типа О, то в соответствии с п. 1 теоремы 7.2 классы языков типа О и ОКЗ-языков совпадают. В силу н. 2 того же утверждения, а также ввиду того, что любая КЗ-грамматика является неукорачивающей грамматикой, совпадают классы неукорачивающих и КЗ-языков.
В силу пп. 3 и 4 теоремы 7.2 совпадают классы право-, леволинейных и регулярных юыков. Но можно доказать следующие факты. Теорема 7,3. 1. Существует ОКЗ-язык, не являющийся КЗ-языком. 2. Существует КЗ-язык, не являющийся КС-языком. 3. Существует КС-язык, не являющийся линенным языком. 4. Существует линенный язык, не являющийся регулярным язьпсом. ф Некоторые ю утверждений теоремы 7.3 мы докажем позже. Сейчас заметим только, что языки, порождаемые грамматиками 04 и Сз ю примера 7.5, не являются КС-языками, хотя для языка, порождаемого грамматикой Сз, можно построить порождающую его КЗ-грамматику.
Язык правильных скобочных структур, порождаемый грамматикой Сз ю примера 7.5, не является линейным языком, а язык палиндромов ю примера 7.6 не есть регулярный юык. Итак, можно утверждать, что имеют место следующие строгие включения классов языков: РЕГСЛИНс КССОКЗ=ТИП О; КЗСОКЗ, 490 Т. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ где РЕГ, ДИН, КС, КЗ, ОКЗ, ТИП 0 — классы регулярных, линейных, КС-языков, КЗ-языков, ОКЗ-языков и языков типа 0 соответственно.
Замечание 7.3. В силу п. 1 теоремы 7.3 требование, состоящее в том, чтобы в КЗ-правиле уф -+ <р~ф цепочка ( была непустой, является принципиальным. В 8.2 мы докажем, что с определенными оговорками класс КС-языков можно включить в класс КЗ-языков, поскольку любую КС-грамматику можно преобразовать к эквивалентной КС-грамматике, не содержа щей правила вывода вида А -+ Л.
Принципиальное различие между классификацией грамматик и языков состоит в следующем. Чтобы определить класс грамматики, достаточно посмотреть на множество ее правил вывода. Чтобы доказать „положительное" утверждение о том, что заданный язык есть язык такого-то класса, достаточно придумать любую грамматику из соответствующего класса, которая его порождает. Но чтобы доказать „отрицательное" утверждение о классе языка, т.е. доказать, что язык не принадлежит такому-то классу языков, нужно доказать, что не существует грамматики соответствующего класса, которая его порождает. Эта задача гораздо труднее.
Некоторые методы построения подобных доказательств будут рассморены далее. 7.4. Регулярные языки н регулярные выражения В замкнутпом полукольце х,(У) всех языков в алфавите У рассмотрим подалгебру, порождеииую миожестпео, которое состоит иэ пустого языка, языка (Л), всех языков (а1, а е У (каждый из которых содержит единственную однобуквенную цепочку а), и замкнутпую отпноситпельно итперации.
Эта подалгебра, обозначаемая Я(У), есть полукольцо с итперациеб. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом резуллрных языков. Далее будет 7.4. Регуллряые языки в регуллряые выракелвл 491 доказано,что элементы полукольца Я(У) являются в точности регулярными языками, т.е. языками, порождаемыми регулярными грамматаиками. Теорема 7.4. Язык в алфавите У регулярен тогда и только тогда, когда он являетсл элементом полукольца Я.(У). Здесь мы не будем доказывать зту теорему, а выведем ее позже, опираясь на другие теоремы о регулярных языках (см.
7.5). Таким образом, множество регулярных языков в алфавите У = (а1, ..., а„) есть не что иное, как замыкание конечного множества (И, (Л), (а1 ), ..., (а„)) оп~носитеяьно операииб объединения, соединения и итерации. Следовательно, как и всякое й-замыкание, оно может быть описано индуктивно (см. 4.1), а именно: 1) пустое множество И, множество (Л) (состоящее из одной пустой цепочки) и множество (а) для каждого а е У считаем регулярным языком в алфавите У; 2) если известно, что Р и 14 — регулярные языки в алфавите У, то к множеству регулярных языков в алфавите У следует добавить объединение Р О Ь7 и соединение Рь4; 3) если известно, что Р— регулярный язык в алфавите У, то к множеству регулярных языков в алфавите У следует добавить его итерацию Р', 4) никаких других регулярных языков, кроме определенных в пп. 1 — 3, не существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
