Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Классификация грамматик и языков

Классификация грамматик и языков


Напомним, что единственное ограничение, накладываемое на правило вывода любой грамматики, состоит в том, что в левую часть правила должен входить хотя бы один нетерминал. В зависимости от дополнительных ограничений, накладываемых на правила вывода грамматики, различают следующие основные классы грамматик.


1. Грамматики типа 0, или грамматики общего вида. Здесь на правила вывода не накладывается никаких дополнительных ограничений.


2. Неукорачивающие грамматики. Каждое правило такой грамматики имеет вид \alpha\to\beta, где |\alpha|\leqslant|\beta|. Таким образом, длина правой части правила не меньше длины левой. Грамматика G_4 из примера 7.5 есть неукорачивающая грамматика, но грамматика G_5 из того же примера таковой не является.


3. Контекстно-зависимые грамматики (КЗ-грамматики). Грамматику называют контекстно-зависимой грамматикой (КЗ-грамматикой), если любое ее правило вывода имеет вид \varphi A\psi\to\varphi\xi\psi, где A — нетерминал, \xi — некоторая цепочка, \xi\ne\lambda. Каждое такое правило, называемое КЗ-правилом, позволяет заменить нетерминал A в "контексте", образуемом цепочками \varphi и \psi в объединенном алфавите, непустой цепочкой \xi (см. замечание 7.1). Иногда цепочку \varphi называют левым контекстом, а цепочку \psi — правым контекстом данного КЗ-правила. Из определения видно, что каждая КЗ-грамматика является неукорачивающей.


Грамматика G_4 из примера 7.5 не является КЗ-грамматикой, так как правило CB\to BC не является КЗ-правилом. Остальные же правила вывода этой грамматики — КЗ-правила. Грамматика G_5 из примера 7.5 не является КЗ-грамматикой хотя бы из-за наличия правила вывода с пустой правой частью. КЗ-грамматикой является грамматика из примера 7.3.


Если в КЗ-правиле снять требование непустоты цепочки \xi, то получим грамматику, которую называют обобщенной КЗ-грамматикой (или, коротко, ОКЗ-грамматикой).


4. Контекстно-свободные грамматики (КС-грамматики). Каждое правило такой грамматики имеет вид A\to\alpha, т.е. левая часть каждого правила вывода есть нетерминал, а правая — произвольная (может быть и пустая) цепочка в объединенном алфавите.


С практической точки зрения это наиболее важный класс грамматик, поскольку именно в терминах КС-грамматик описывается синтаксис языков программирования, и этим грамматикам будет посвящена отдельная глава. Грамматики G_2,G_3,G_4 из примера 7.5 являются КС-грамматиками.


5. Линейные грамматики. Каждое правило такой грамматики имеет вид A\to uBv или A\to u, т.е. в правой части правила может содержаться не более одного вхождения нетерминала. Если во всех правилах вида A\to uBv имеет место v=\lambda, то грамматика называется праволинейной, а если u=\lambda — леволинейной.


Пример 7.6. Линейной является грамматика G_6=(\{a_1,\ldots,a_n\}, \{S\},S, P_6), где множество правил вывода P_6 есть


S\to a_1Sa_1\mid a_2Sa_2\mid \ldots a_nSa_n\mid a_1\mid a_2\mid \ldots a_n\mid \lambda\,.

Можно доказать, что эта грамматика порождает все палиндромы в алфавите V, т.е. все цепочки, читаемые слева направо так же, как и справа налево. Например, для V=\{a,b,c\} цепочка acbbca — палиндром. Вывод его в грамматике G_6 (для данного терминального алфавита) будет иметь вид


S\vdash aSa\vdash acSca\vdash acbSbca\vdash acb\lambda bca=acbbca.

Замечание 7.2. Формальное определение палиндрома таково. Назовем инверсией непустой цепочки


x=x(1)x(2)\ldots x(k-1)x(k)\in V цепочку x^R=x(k)x(k-1)\ldots x(2)x(1)..

Для пустой цепочки \lambda по определению считаем \lambda^R= \lambda. Палиндром в алфавите V — это любая цепочка x, для которой x^R=x.


6. Регулярные грамматики. У такой грамматики каждое правило имеет вид A\to aB или A\to a, где a есть либо терминал, либо пустая цепочка. Регулярные грамматики — частный случай праволинейных грамматик.


Эти грамматики подробно будут рассмотрены в следующей лекции.




Утверждения о классах грамматик


Приведем без доказательства некоторые утверждения о классах грамматик.


Теорема 7.2.1. Для любой грамматики типа 0 может быть построена эквивалентная ей ОКЗ-грамматика.

2. Для любой неукорачивающей грамматики может быть построена эквивалентная ей КЗ-грамматика.

3. Для любой леволинейной грамматики может быть построена эквивалентная ей праволинейная грамматика, и, наоборот, для любой праволинейной грамматики может быть построена эквивалентная ей леволинейная грамматика.

4. Для любой праволинейной грамматики может быть построена эквивалентная ей регулярная грамматика.


Отметим, что доказательства первых двух пунктов теоремы 7.2 весьма нетривиальны.


Классификация языков, порождаемых грамматиками, тесно связана с классификацией самих грамматик, хотя и не тождественна ей. Язык относят к классу C, если существуем грамматика класса C, порождающая данный язык. Таким образом определяются языки типа 0, неукорачивающие языки, контекстно-зависимые языки (КЗ-языки), обобщенные контекстно-зависимые языки (ОКЗ-языки), контекстно-свободные языки (КС-языки), линейные языки, право- и леволинейные языки, регулярные языки.


Так как всякая ОКЗ-грамматика является грамматикой типа 0, то в соответствии с пункт 1 теоремы 7.2 классы языков типа О и ОКЗ-языков совпадают. В силу пункт 2 того же утверждения, а также ввиду того, что любая КЗ-грамматика является неукорачивающей грамматикой, совпадают классы неукорачивающих и КЗ-языков. В силу пункты 3 и 4 теоремы 7.2 совпадают классы право-, леволинейных и регулярных языков.


Но можно доказать следующие факты.


Теорема 7.3. 1. Существует ОКЗ-язык, не являющийся КЗ-языком.

2. Существует КЗ-язык, не являющийся КС-языком.

3. Существует КС-язык, не являющийся линейным языком.

4. Существует линейный язык, не являющийся регулярным языком.


Некоторые из утверждений теоремы 7.3 мы докажем позже. Сейчас заметим только, что языки, порождаемые грамматиками G_4 и G_5 из примера 7.5, не являются КС-языками, хотя для языка, порождаемого грамматикой G_5, можно построить порождающую его КЗ-грамматику. Язык правильных скобочных структур, порождаемый грамматикой G_3 из примера 7.5, не является линейным языком, а язык палиндромов из примера 7.6 не есть регулярный язык.


Итак, можно утверждать, что имеют место следующие строгие включения классов языков:


РЕГ \subset ЛИН \subset КС \subset ОКЗ = ТИП 0; КЗ \subset ОКЗ,

где РЕГ, ЛИН, КС, КЗ, ОКЗ, ТИП 0 — классы регулярных, линейных, КС-языков, КЗ-языков, ОКЗ-языков и языков типа 0 соответственно.


Замечание 7.3. В силу п. 1 теоремы 7.3 требование, состоящее в том, чтобы в КЗ-правиле \varphi A\psi\to\varphi\xi\psi цепочка \xi была непустой, является принципиальным. В одной из следующих лекций мы докажем, что с определенными оговорками класс КС-языков можно включить в класс КЗ-языков, поскольку любую КС-грамматику можно преобразовать к эквивалентной КС-грамматике, не содержащей правила вывода вида A\to\lambda.


Принципиальное различие между классификацией грамматик и языков состоит в следующем. Чтобы определить класс грамматики, достаточно посмотреть на множество ее правил вывода. Чтобы доказать "положительное" утверждение о том, что заданный язык есть язык такого-то класса, достаточно придумать любую грамматику из соответствующего класса, которая его порождает. Но чтобы доказать "отрицательное" утверждение о классе языка, т.е. доказать, что язык не принадлежит такому-то классу языков, нужно доказать, что не существует грамматики соответствующего класса, которая его порождает. Эта задача гораздо труднее. Некоторые методы построения подобных доказательств будут рассмотрены далее.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved