Эквивалентность (формальные языки) - Википедия - Equivalence (formal languages)

В формальной теории языка слабая эквивалентность из двух грамматики означает, что они генерируют один и тот же набор строк, т.е. формальный язык они генерируют то же самое. В теория компилятора это понятие отличается от сильный (или же структурный) эквивалентность, что дополнительно означает, что два разбирать деревья[требуется разъяснение ] достаточно похожи в том смысле, что им обоим может быть назначена одинаковая семантическая интерпретация.[1]

Виджай-Шанкер и Вейр (1994)[2] демонстрирует, что Линейные индексированные грамматики, Комбинаторные категориальные грамматики, Грамматики, примыкающие к дереву, и Головные грамматики являются слабо эквивалентными формализмами,[требуется разъяснение ] в том, что все они определяют одни и те же строковые языки.

С другой стороны, если две грамматики генерируют один и тот же набор производных деревьев (или, в более общем смысле, один и тот же набор абстрактных синтаксических объектов), то эти два языка строго эквивалентны. Хомский (1963)[3] вводит понятие строгой эквивалентности и утверждает, что при сравнении грамматических формализмов уместна только строгая эквивалентность. Корнаи и Пуллум (1990)[4] и Миллер (1994)[5] предлагают уточненное понятие строгой эквивалентности, которое допускает изоморфные отношения между синтаксическим анализом, данным различными формализмами. Ёсинага, Мияо и Цуджи (2002)[6] предлагает доказательство сильной эквивалентности LTAG и HPSG формализмы.

Пример бесконтекстной грамматики

Оставили: одно из деревьев синтаксического анализа строки «1 + 2 * 3» с первой грамматикой. Правильно: единственное дерево синтаксического анализа этой строки со второй грамматикой.

В качестве примера рассмотрим следующие два контекстно-свободные грамматики,[примечание 1] приведены в Форма Бэкуса-Наура:

<выражение> ::= <выражение> "+" <выражение> | <выражение> "-" <выражение>               | <выражение> "*" <выражение> | <выражение> "/" <выражение>                | «х» | "у" | "z" | «1» | «2» | «3» | "(" <выражение> ")"
<выражение> ::= <срок>   | <выражение> "+" <срок>   | <выражение> "-" <срок><срок>       ::= <фактор> |       <срок> "*" <фактор> |       <срок> "/" <фактор><фактор>     ::= «х» | "у" | "z" | «1» | «2» | «3» | "(" <выражение> ")"

Обе грамматики генерируют один и тот же набор строк, а именно. набор всех арифметических выражений, которые можно построить из переменных «x», «y», «z», констант «1», «2», «3», операторов «+», «-», « * "," / "и круглые скобки" ("и") ". Однако конкретное синтаксическое дерево второй грамматики всегда отражает обычный порядок действий, а дерево из первой грамматики не нужно.

Для примера строки «1 + 2 * 3» в правой части рисунка показано уникальное дерево синтаксического анализа со второй грамматикой;[заметка 2] оценивая это дерево в постфиксный порядок даст правильное значение 7. Напротив, левая часть рисунка показывает одно из деревьев синтаксического анализа для этой строки с первой грамматикой; оценка его в постфиксном порядке даст 9.

Поскольку вторая грамматика не может генерировать дерево, соответствующее левой части изображения, в то время как первая грамматика может, обе грамматики не являются строго эквивалентными.

Генерирующая мощность

В лингвистике слабая генеративная способность из грамматика определяется как набор всех сгенерированных им строк,[заметка 3] в то время как грамматика сильная генеративная способность относится к набору «структурных описаний»[примечание 4] порожденный им.[7]Как следствие, две грамматики считаются слабо эквивалентными, если их слабые порождающие способности совпадают; аналогично для сильной эквивалентности. генерирующая способность был представлен Ноам Хомский в 1963 г.[3][7]

Примечания

  1. ^ с начальный символ «<выражение>»
  2. ^ с использованием сокращений «E», «T» и «F» для , и соответственно
  3. ^ для контекстно-свободных грамматик: см. Грамматика без контекста # Язык без контекста для формального определения
  4. ^ для контекстно-свободных грамматик: конкретные синтаксические деревья

Рекомендации

  1. ^ Стефано Креспи Регицци (2009). Формальные языки и компиляция. Springer. п. 57. ISBN  978-1-84882-049-4.
  2. ^ Виджай-Шанкер К. и Вейр Дэвид Дж. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик». Математическая теория систем. 27 (6): 511–546.CS1 maint: несколько имен: список авторов (связь)
  3. ^ а б Ноам Хомский (1963). «Формальные свойства грамматики». В R.D. Luce; Р. Р. Буш; Э. Галантер (ред.). Справочник по математической психологии. II. Нью-Йорк: Вили. стр.323 —418.
  4. ^ Корнаи А. и Пуллум Г. К. 1990. X-bar теория структуры фраз. Язык, 66: 24-50.
  5. ^ Миллер, Филип Х. 1999. Сильная генерирующая способность. Публикации CSLI.
  6. ^ Ёсинага Н., Мияо Ю. и Цуджи Дж. 2002. Формальное доказательство строгой эквивалентности преобразования грамматики из LTAG в HPSG. В материалах семинара TAG + 6: 187-192. Венеция, Италия" (PDF). Архивировано из оригинал (PDF) на 2011-08-28. Получено 2012-02-05.
  7. ^ а б Эммон Бах; Филип Миллер (2003). «Генерирующая способность» (PDF). В Уильяме Дж. Фроули (ред.). Международная энциклопедия лингвистики (2-е изд.). Издательство Оксфордского университета. Дои:10.1093 / acref / 9780195139778.001.0001. ISBN  9780195139778.