Обобщенная контекстно-свободная грамматика (GCFG) - это грамматический формализм, который расширяет контекстно-свободные грамматики , добавляя потенциально неконтекстные функции композиции для перезаписи правил. [1] Головная грамматика (и ее слабые эквиваленты) является примером такой GCFG, которая, как известно, особенно хорошо справляется с широким спектром не-CF свойств естественного языка.
Описание
GCFG состоит из двух компонентов: набора функций композиции, которые объединяют строковые кортежи, и набора правил перезаписи. Все функции композиции имеют вид, где представляет собой либо одностроковый кортеж, либо некоторое использование (потенциально другой) функции композиции, которая сводится к строковому кортежу. Правила перезаписи выглядят так, где , , ... - строковые кортежи или нетерминальные символы.
Семантика перезаписи GCFG довольно проста. Появление нетерминального символа переписывается с использованием правил перезаписи, как в контекстно-свободной грамматике, что в конечном итоге дает просто композиции (функции композиции, применяемые к строковым кортежам или другим композициям). Затем применяются функции композиции, последовательно сокращая кортежи до одного кортежа.
Пример
Простой перевод контекстно-свободной грамматики в GCFG можно выполнить следующим образом. Учитывая грамматику в ( 1 ), которая порождает язык палиндромов, где это строка, обратная , мы можем определить композиционную функцию conc, как в ( 2a ), и правила перезаписи, как в ( 2b ).
( 1 )
( 2а )
( 2b )
Производство CF из abbbba является
- S
- как
- abSba
- abbSbba
- Abbbba
и соответствующая продукция GCFG равна
Линейные системы перезаписи без контекста (LCFRS)
Weir (1988) [1] описывает два свойства композиционных функций: линейность и регулярность. Функция, определенная какявляется линейным тогда и только тогда, когда каждая переменная появляется не более одного раза по обе стороны от = , что делает линейный, но не . Функция, определенная как является регулярным, если левая и правая части имеют точно такие же переменные, что делает обычный, но не или же .
Грамматика, в которой все функции композиции являются как линейными, так и регулярными, называется линейной системой перезаписи без контекста (LCFRS). LCFRS является надлежащим подклассом GCFG, т. Е. Имеет строго меньшую вычислительную мощность, чем GCFG в целом.
С другой стороны, LCFRS строго более выразительны, чем грамматики с линейным индексом и их слабо эквивалентное дерево вариантов, примыкающих к грамматикам (TAG). [2] Головная грамматика - еще один пример LCFRS, который строго менее эффективен, чем класс LCFRS в целом.
LCFRS слабо эквивалентны (локально установленным) многокомпонентным тегам ( MCTAG ), а также с множественной контекстно-свободной грамматикой (MCFG [1] ). [3] и минималистские грамматики (MG). Языки, сгенерированные LCFRS (и их слабые эквиваленты), могут быть проанализированы за полиномиальное время . [4]
Смотрите также
Рекомендации
- ^ Б Weir, Дэвид Джереми (сентябрь 1988). Описание слабо контекстно-зависимых грамматических формализмов (PDF) (доктор философии). Бумага. AAI8908403. Пенсильванский университет в Анн-Арборе.
- ^ Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик . Springer Science & Business Media. п. 33. ISBN 978-3-642-14846-0.
- ^ Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик . Springer Science & Business Media. п. 35-36. ISBN 978-3-642-14846-0.
- ^ Йохан Ф.К. ван Бентем; Алиса тер Мёлен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ISBN 978-0-444-53727-0.