В теории формальных языков , растет контекстно-зависимая грамматика является контекстно-зависимая грамматика , в которой производство увеличится длина предложений генерируется. [1] [2] Таким образом, эти грамматики не связаны с контрактами и зависят от контекста. Растет контекстно-зависимый язык является контекстно-зависимый язык , порожденный этими грамматик.
В этих грамматиках «начальный символ» S не появляется с правой стороны какого-либо производственного правила, а длина правой стороны каждой продукции превышает длину левой стороны, если только левая сторона не является S. [1]
Эти грамматики были введены Дальхаусом и Вармутом. [3] Позже было показано, что они эквивалентны ациклическим контекстно-зависимым грамматикам . [3] Членство в любом растущем контекстно-зависимом языке вычислимо за полиномиальное время ; [4] [5], однако, универсальная проблема определения того, принадлежит ли данная строка языку, генерируемому данной растущей [6] или ациклической [7] контекстно-зависимой грамматикой, является NP-полной .
Смотрите также
Рекомендации
- ^ a b Г. Бантрок и Ф. Отто (1995). «Развитие контекстно-зависимых языков и языков Чёрча-Россера». В Эрнст В. Майр и Клод Пуэх (ред.). Proc. 12-й СТЭКС . LNCS. 900 . Springer. С. 313–324. ISBN 978-3540590422. Здесь: с.316-317
- ^ Герхард Бантрок и Фридрих Отто (1998). «Развитие контекстно-зависимых языков и языков Чёрча-Россера». Информация и вычисления . 141 : 1–36. DOI : 10.1006 / inco.1997.2681 .
- ^ а б Гундула Ниманн и Йенс Р. Войновски (2002). «Растущие контекстно-зависимые языки являются ациклическими контекстно-зависимыми языками». У Вернера Куича и Гжегожа Розенберга и Арто Саломаа (ред.). Proc. 5-й Int. Конференция по развитию теории языка (DLT) . Конспект лекций по информатике. 2295 . Springer. С. 197–205. ISBN 978-3540434535.. Здесь: с.197-198
- ^ Э. Дальхаус и М.К. Вармут (1986). «Членство в растущих контекстно-зависимых грамматиках является полиномиальным». В Поля Франки-Заннеттаччи (ред.). Proc. 11-й коллоквиум по деревьям в алгебре и программировании (CAAP) (PDF) . LNCS. 214 . Springer. С. 85–99. Здесь: с.85-86
- ^ Э. Дальхаус и М.К. Вармут (1986). «Членство в растущих контекстно-зависимых грамматиках является полиномиальным». Журнал компьютерных и системных наук . 33 (3): 456–472. DOI : 10.1016 / 0022-0000 (86) 90062-0 .
- ^ Г. Бантрок и К. Лорис. О растущих контекстно-зависимых языках. В Proc. 19-й ICALP, Lecture Notes in Computer Science (W. Kuich, ed, стр. 77–88. Springer-Verlag, 1992.
- ^ Эрик Аартс (1992). «Единое распознавание контекстно-зависимых грамматик является NP-полным» (PDF) . Proc. 14-й Int. Конф. по компьютерной лингвистике (COLING, Нант, 23–28 августа) . С. 1157–1161.
Внешние ссылки
- Г. Бантрок: Развитие контекстно-зависимых языков