Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 12

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 136 >> Следующая

Два вывода в грамматике Г назовем равносильным и, если их первые и последние цепочки соответственно совпадают.
Вывод, в котором никакая цепочка не встречается более одного раза, назовем бесповторным.
Лемма 1.3. Для произвольного вывода в любой грамматике существует равносильный ему бесповторный вывод, который можно получить из исходного выбрасы-ванием некоторых цепочек. Доказательство очевидно.
Грамматики Г.и Г' называются эквивалентными, если L(r) = L(T').
32 основные понятия [гл.
Лемма 1.4. Для произвольной грамматики Г жет быть построена *) эквивалентная ей грамматика Г; левые части правил которой не содержат вхождени основных символов. Если при этом Г — НС-грамматик то и Г' может быть сделана НС-грамматикой.
Доказательство. Пусть T — (V,W,i,R). Сопо ставим каждому символу neF «двойника» — новы символ афУ U№ — так, чтобы разным символам от вечали разные «двойники». Положим F = {a|aeV} Y'=(V, W[j V, I, RU /?}, где /? = {а-о|оеУ} и получается из R заменой в каждом правиле все вхождений основных символов вхождениями их «двойников». Легко видеть, что Г' и есть нужная грамматика.
В грамматике, удовлетворяющей условию леммы 1.4, каждое правило, правая часть которого непуста и состоит из основных символов, является заключительным.
Пусть — некоторый класс грамматик и ср — ^-местная операция над языками. Допуская языковую воль-г ность, будем говорить, что класс S(Т) эффективно: замкнут относительно ср, если по любым k грамма-; тикам Ti, ..., Гь е можно построить такую грамматику ГеГ, что ?(Г) =ф(?(Г1), ..., L(Th)) **).
Теорема 1.1. Класс языков, порождаемых всевозможными грамматиками, эффективно замкнут относительно операций объединения, пересечения, умножения, итерации, усеченной итерации, левого и правого деления и подстановки.
Доказательство. 1) Пусть Г' = (F7, W',I',Rr) и Г" — (V", W",I",R") — произвольные грамматики. В силу леммы 1.4 мы можем считать, что левые части правил Г7 и Г" не содержат вхождений основных символов. Будем считать, кроме того, что W' П W" = 0; если это не так, переименуем символы, входящие в W", что не изменит языка L(V"). При выполнении этих условий очевидно, что грамматики (V,W,I, R U R" U {/ -> I',
*) «Построить» будет на протяжении всей книги означать «эффективно построить». Здесь, например, «по произвольной грамматике Г может быть построена Г'» означает «существует алгоритм, строящий по произвольной грамматике Г нужную Г'»; в дальнейшем всюду аналогично.
**) Таким образом, эффективная замкнутость есть на самом деле свойство класса Э~, а не класса
ПРИМЕРЫ ГРАММАТИК
33
/ — /"}) и (V,W,I, R'\JR"U{I-+I'I"}), где V = =« I/' U V", W=W' и W" и {/}, / ф V' и V" и W и W",
порождают соответственно языки L{T') U L(r") и L(Y')L(Y"). Чтобы построить грамматику, порождающую пересечение, сопоставим взаимно однозначным образом каждому символу а V' новый символ а и каждому символу V" новый символ Ь^_ Положим V' = =* {а|а <= V'},_V" = {b\Ъ е= V"} (Р'П F" = 0). Обозначим через R', соответственно через R", множество правил, полученное из R’ (из R") заменой каждого вхождения каждого основного символа а в каждое правило вхождением символа а (а). Пусть теперь \JV"lJV'UV'/UW'l)W" и t T = (V'(]V", W'UW"UV'\)V"\){I}, I, R'UR"U
у^тил.ий
где Ri={aF-> Га | aeV', &eV"}, #2={aa -> a | aeF' fl У17}. Нетрудно видеть, что L (Г) = L (Г') П ? (Г").
2) Пусть Г = (у, W, /, R) — произвольная грамма-
тика. Как и выше, считаем, что левые части ее правил не содержат вхождений основных символов. Пусть х — произвольная цепочка из V*. Положим W'— W\}{I', #}, где I',#&V\]W, «'={/'->#и U{#a->a#|ae=V}, #*^Л}. Легко
видеть, что грамматики Г = (V, W', I', R U R') и Г* = (V, W', Г, R U Rx) порождают соответственно языки L (Г)+ и x\L (Г). Чтобы получить язык L (Г)’, достаточно добавить к схеме грамматики Г' правило /'-> А. Грамматика для L{T)/x строится аналогично Г*.
3) Доказательство для подстановки предоставляется читателю.
Замечание. Относительно операций вычитания и взятия дополнения рассматриваемый класс языков не замкнут (см. ниже замечание в конце § 1.4).
§ 1.3. Примеры грамматик
Во всех приводимых здесь и далее примерах грамматик мы будем, если не оговорено противное, обозначать основные символы строчными латинскими буквами,
2 А. В. Гладкий
34
ОСНОВНЫЕ понятия
[ГЛ. I
вспомогательные — заглавными латинскими буквами (те и другие буквы могут иметь индексы и надстрочные знаки), начальный символ — буквой I. Это позволит нам ограничиться выписыванием схем грамматик.
Пример 1. а) Любой непустой конечный язык 1 {coi, ..., соп}, оэг Ф А, порождается Б-грамматикой со схемой {/ —»? oil, ..., / —? соп}-
б) Тот же язык, если щ — а... aiki, порождается А-грамматикой со схемой
{Ato^-ацАц, •••> Ai,kl-2^>'ai,ki-\Ai,kl-1>
Ai.kr\-*ai.ki\i=^ •••> п),
где Л10 = ... = Лп0 = /.
в) Пустой язык порождается А-грамматикой со схемой {/ —? а/}.
Таким образом, любой конечный язык, не содержащий А, является А-языком.
Пример 2. Для любого словаря V язык У+ порождается А-грамматикой со схемой {/—>а/, /-*а|ае V).
Будем называть простейшей записью натурального числа п цепочку || ...|. Множество простейших
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed