Обобщенная контекстно-свободная грамматика

Обобщенная контекстно-свободная грамматика (GCFG) — это грамматический формализм, который расширяет контекстно-свободные грамматики путем добавления потенциально неконтекстно-свободных функций композиции для перезаписи правил. ^[1] Головная грамматика (и ее слабые эквиваленты) является примером такой GCFG, которая, как известно, особенно хорошо справляется с широким спектром свойств естественного языка, не относящихся к CF.

Описание

GCFG состоит из двух компонентов: набора функций композиции, объединяющих строковые кортежи, и набора правил перезаписи. Все функции композиции имеют вид $f(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma$ , где $\gamma$ представляет собой либо один строковый кортеж, либо использование (потенциально другой) функции композиции, которая сводится к строковому кортежу. Правила перезаписи выглядят так $X\to f(Y,Z,...)$ , где $Y$ , $Z$ , ... являются строковыми кортежами или нетерминальными символами.

Семантика перезаписи GCFG довольно проста. Появление нетерминального символа перезаписывается с использованием правил перезаписи, как в контекстно-свободной грамматике, что в конечном итоге дает только композиции (функции композиции, применяемые к строковым кортежам или другим композициям). Затем применяются функции композиции, последовательно сводящие кортежи к одному кортежу.

Пример

Простой перевод контекстно-свободной грамматики в GCFG можно выполнить следующим образом. Учитывая грамматику в ( 1 ), которая генерирует язык палиндромов $\{ww^{R}:w\in \{a,b\}^{*}\}$ , где $w^{R}$ это строка, обратная $w$ , мы можем определить функцию композиции conc, как в ( 2a ), и правила перезаписи, как в ( 2b ).

S\to \epsilon ~|~aSa~|~bSb

( 1 )

conc(\langle x\rangle ,\langle y\rangle ,\langle z\rangle )=\langle xyz\rangle

( 2а )

S\to conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle )~|~conc(\langle a\rangle ,S,\langle a\rangle )~|~conc(\langle b\rangle ,S,\langle b\rangle )

( 2б )

Производство Abbba в CF

С

аса

АбСба

аббСбба

аббба

и соответствующее производство GCFG равно

S\to conc(\langle a\rangle ,S,\langle a\rangle )

conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )

conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )

conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )

conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )

conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )

conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )

\langle abbbba\rangle

Линейные бесконтекстные системы переписывания (LCFRS)

Вейр (1988) ^[1] описывает два свойства композиционных функций: линейность и регулярность. Функция, определенная как $f(x_{1},...,x_{n})=...$ является линейным тогда и только тогда, когда каждая переменная появляется не более одного раза по обе стороны от = , что делает $f(x)=g(x,y)$ линейный, но не $f(x)=g(x,x)$ . Функция, определенная как $f(x_{1},...,x_{n})=...$ является регулярным, если левая и правая части имеют одни и те же переменные, что делает $f(x,y)=g(y,x)$ обычный, но нет $f(x)=g(x,y)$ или $f(x,y)=g(x)$ .

Грамматика, в которой все функции композиции одновременно линейны и регулярны, называется линейной системой контекстно-свободной переписывания (LCFRS). LCFRS является собственным подклассом GCFG, т.е. он имеет строго меньшую вычислительную мощность, чем GCFG в целом.

С другой стороны, LCFRS строго более выразительны, чем грамматики с линейным индексом и их слабо эквивалентные вариантов грамматики, примыкающие к дереву (TAG). ^[2] Головная грамматика — еще один пример LCFRS, который строго менее мощный, чем класс LCFRS в целом.

LCFRS слабо эквивалентны (множественно-локальным) многокомпонентным TAG ( MCTAG ), а также с множественной контекстно-свободной грамматикой (MCFG [1] ). ^[3] и минималистские грамматики (MG). Языки, созданные LCFRS (и их слабые эквиваленты), можно анализировать за полиномиальное время . ^[4]

См. также

Грамматика конкатенации диапазонов

Ссылки

^ Jump up to: ^а ^б Вейр, Дэвид Джереми (сентябрь 1988 г.). Характеристика слегка контекстно-зависимых грамматических формализмов (PDF) (доктор философии). Бумага. Том. ААИ8908403. Пенсильванский университет в Анн-Арборе.
^ Лаура Каллмейер (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. ИСБН 978-0-444-53727-0 .

[weir1988-1] Jump up to: ^а ^б Вейр, Дэвид Джереми (сентябрь 1988 г.). Характеристика слегка контекстно-зависимых грамматических формализмов (PDF) (доктор философии). Бумага. Том. ААИ8908403. Пенсильванский университет в Анн-Арборе.

[Kallmeyer2010-2] Лаура Каллмейер (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. п. 33. ISBN 978-3-642-14846-0 .

[Kallmeyer2010b-3] Лаура Каллмейер (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. п. 35-36. ISBN 978-3-642-14846-0 .

[BenthemMeulen2010-4] Йохан ФАК ван Бентем; Алиса тер Меулен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ИСБН 978-0-444-53727-0 .

[1]

[2]

[3]

[4]