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