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

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

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 47 48 49 50 51 52 < 53 > 54 55 56 57 58 59 .. 136 >> Следующая

Л
излишни.
Р
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
149
то а' состоит из окрестностей
/\а;А , /\" ,.... /tf"
L А? 4г-1 <А ?л J Lftf. ;:вф J
при р>2
и
\ при р-г.
L Р* дВфгА
Замечания. 1) Процедуры, примененные при доказательстве лемм 4.12, а) и 4.13,6), устанавливают, как легко убедиться, взаимно однозначное соответствие между множеством деревьев полных выводов ОБ-грам-матики и множеством упрощенных деревьев полных вычислений эквивалентной ей МП-машины, и при этом соответствии сохраняются отвечающие деревьям цепочки основных символов. Аналогичный факт верен для процедур лемм 4.13, а), 4.12, 6) и 4.14.
2) Пусть для произвольной ОБ-грамматики Г выражение ?с(Г) означает множество всевозможных систем составляющих для цепочек языка ?(Г), соответствующих деревьям выводов этих цепочек в Г. Аналогичный смысл придадим обозначению Lc{M), где М — МП-ма-шина. Тогда доказательства лемм 4.12, а) и 4.13,6) дают способ для всякой ОБ-грамматики Г построить такую МП-машину М, что LC{M) = ?с(Г). Обратное, очевидно, неверно: если ширина множества LC(M) не ограничена (т. е. не существует числа, мажорирующего ширину любой системы из LC(M)), то ни для какой ОБ-грамматики Г равенство LC(T) = LC(M) невозможно. Но если ширина множества LC(M) ограничена и ограничивающее ее число известно, то ОБ-грамматика Г, удовлетворяющая указанному равенству, может быть построена. Для этого придется несколько усложнить конструкцию пункта а) леммы 4.13, моделируя не пары соседних дуг дерева вычисления, а целые кусты — это
150 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОИ ПАМЯТЬЮ [ГЛ. 4
становится возможным ввиду ограниченности числа дуг в них; тогда отпадет надобность в лемме 4.14, т. е. в изменении топологии дерева.
Подробное проведение соответствующих построений предоставляется читателю. Вместе с результатом упражнения -4.28 это позволяет для каждой МП-машины М либо построить ОБ-грамматику Г такую, что ?с(Г) = .= LC(M), либо установить, что такой грамматики нет.
3) Пусть Сх — система составляющих цепочки х, отвечающая некоторому дереву вычисления МП-машины М, и магма составляющих той же цепочки, отвечающая соответствующему дереву вывода в Б-грамма-тике, построенной по М с помощью процедур лемм 4.13, а), 4.14 и 4.12,6). Если у— произвольная неточечная составляющая системы Сх (точнее, соответствующая . подцепочка цепочки х) и если у = ... zs, где
zu 22, ..., zs — составляющие, непосредственно вложенные в у, то все отрезки у = Ziz2 ... ze, гг ... zs, ... ..., zs-izs принадлежат С'х. При этом все неточечные составляющие системы С'х могут быть получены таким способом. Сверх того, метки новых составляющих вполне определяются метками непосредственно содержащих их старых.
Естественно возникает вопрос о единственгости дерева вычисления для данной входной цепочки. По аналогии с понятием однозначной Б-грамматики напрашивается следующее определение: МП-машина М называется о д н о з н_а ч н о й, если для каждой цепочки x^L(M) существует единственное дерево полного х-вычисления (или, что то же самое, единственное полное х-вычисление).
Машины примеров 1 и 2 на стр. 137—138, как легко видеть, однозначны, а машины примера 3 — нет (упражнение 4.29).
Что касается понятия однозначного ОБ-языка, то оно не изменится, если определить его с помощью МП-машины: имеет место
Теорема 4.10. ОЪ-язык тогда и только тогда однозначен, когда существует допускающая его однозначная МП-машина.
Доказательство немедленно получается из замечания 1) к леммам 4.12, 4.13 и 4.14.
§ 4.51
МАШИНЫ С МАГАЗИННО.И ПАМЯТЬЮ
151
В заключение нам остается уделить немного внимания детерминированным МП-машинам—вернее, тем Б-языкам, которые такими машинами допускаются.
Ясно, прежде всего, что всякая детерминированная МП-машина однозначна, так что неоднозначные Б-язы-ки не допускаются детерминированными МП-машинами. Но и не все однозначные Б-языки допускаются ими. Чтобы в этом убедиться, докажем следующую лемму.
Лемма 4.15. Пусть М — детерминированная МП-машина такая, что L(M)—{Л} не является Р^языком. Тогда найдется цепочка w^L(M), представимая в виде w = ziyixyzzz так, что (a) yt ф А, у% ф А, (6) какова бы ни была цепочка и такая, кто v wke=. L(M)r цепочка vn — zryfxy^z2u также принадлежит L (М).
Доказательство. Пусть сначала w и и — произвольные непустые цепочки такие, что »>, wu е L (М). Ввиду детерминированности машины иш-вычисление, оборванное после чтения последнего символа из w, будет совпадать с ш-вычислением, оборванным после чтения того же символа. При «скобочной» интерпретации вычисления (стр. 141) это означает, что во всяком случае, внутри w при допускании цепочки wu будут поставлены в точности те же скобки ?— и с теми же метками, — что и при допускании w*).
Построим теперь по машине М Б-грамматику Г с помощью процедур лемм 4.13, а), 4.14 и 4.12,6). Если Сх — система составляющих цепочки х, принадлежащая L'c(M), и С'х — соответствующая система составляющих из ?С(Г), т° по предыдущему всякая составляющая из Cw, расположенная целиком внутри w, принадлежит и системе Cwu и имеет в ней в точности те же метки; по замечанию 3) на стр. 150 это верно и для систем C'w и C'wu. В силу следствия из теоремы 7.6 **) грамматика Г имеет неограниченную степень самовставления, и во всяком случае найдется такая цепочка и>е?(Г) = = ?(М), что Яг (яу) ^ 3, — иначе говоря, w представима в виде ZiSitirtzSzZz, где Si, s2, tu t2 ф А и отрезки
Предыдущая << 1 .. 47 48 49 50 51 52 < 53 > 54 55 56 57 58 59 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed