Эквивалентность (формальные языки)

Когда формальные языки генерируют один и тот же набор строк

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

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

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

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

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

< выражение >  ::=  < выражение > "+" < выражение > | < выражение > "-" < выражение > | < выражение > "*" < выражение > | < выражение > "/" < выражение > | "x" | "y" | "z" | "1" | "2" | "3" | "(" < выражение > ")"

< выражение >  ::=  < термин > | < выражение > "+" < термин > | < выражение > "-" < термин > < термин >  ::=  < фактор > | < термин > "*" < фактор > | < термин > "/" < фактор > < фактор >  ::= "x" | "y" | "z" | "1" | "2" | "3" | "(" < выражение > ")"

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

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

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

Генеративная способность

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

Примечания

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

Ссылки

^ Стефано Креспи Регицци (2009). Формальные языки и компиляция. Springer. стр. 57. ISBN 978-1-84882-049-4.
^ Виджай-Шанкер, К. и Вейр, Дэвид Дж. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик». Математическая теория систем . 27 (6): 511– 546. doi :10.1007/BF01191624. S2CID 12336597.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ ab Noam Chomsky (1963). «Формальные свойства грамматики». В RD Luce; RR Bush; E. Galanter (ред.). Справочник по математической психологии. Т. II. Нью-Йорк: Wiley. С. 323—418.
^ Корнай, А. и Пуллум, Г.К. 1990. Теория X-bar структуры фразы . Язык, 66:24-50.
^ Миллер, Филип Х. 1999. Сильный генеративный потенциал . Публикации CSLI.
^ "Ёсинага, Н., Мияо Ё. и Цудзи, Дж. 2002. Формальное доказательство строгой эквивалентности для преобразования грамматики из стиля LTAG в стиль HPSG. В материалах семинара TAG+6:187-192. Венеция, Италия" (PDF) . Архивировано из оригинала (PDF) 28-08-2011 . Получено 05-02-2012 .
^ ab Emmon Bach; Philip Miller (2003). "Generative Capacity" (PDF) . В William J. Frawley (ред.). Международная энциклопедия лингвистики (2-е изд.). Oxford University Press. doi : 10.1093/acref/9780195139778.001.0001. ISBN 9780195139778.

[7] с начальным символом "<выражение>"

[8] используя сокращения «E», «T» и «F» для <выражения>, <терма> и <фактора> соответственно

[9] для контекстно-свободных грамматик: см. Контекстно-свободная грамматика#Контекстно-свободный язык для формального определения

[10] для контекстно-свободных грамматик: конкретные синтаксические деревья

[Reghizzi2009-1] Стефано Креспи Регицци (2009). Формальные языки и компиляция. Springer. стр. 57. ISBN 978-1-84882-049-4.

[vijayshankarAndWeir1995-2] Виджай-Шанкер, К. и Вейр, Дэвид Дж. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик». Математическая теория систем . 27 (6): 511– 546. doi :10.1007/BF01191624. S2CID 12336597.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[Chomsky.1963-3] Noam Chomsky (1963). «Формальные свойства грамматики». В RD Luce; RR Bush; E. Galanter (ред.). Справочник по математической психологии. Т. II. Нью-Йорк: Wiley. С. 323—418.

[kornaiAndPullum1990-4] Корнай, А. и Пуллум, Г.К. 1990. Теория X-bar структуры фразы . Язык, 66:24-50.

[miller1994-5] Миллер, Филип Х. 1999. Сильный генеративный потенциал . Публикации CSLI.

[yoshinagaMiyaoAndTsujii2002-6] "Ёсинага, Н., Мияо Ё. и Цудзи, Дж. 2002. Формальное доказательство строгой эквивалентности для преобразования грамматики из стиля LTAG в стиль HPSG. В материалах семинара TAG+6:187-192. Венеция, Италия" (PDF) . Архивировано из оригинала (PDF) 28-08-2011 . Получено 05-02-2012 .

[Bach.Miller.2003-11] Emmon Bach; Philip Miller (2003). "Generative Capacity" (PDF) . В William J. Frawley (ред.). Международная энциклопедия лингвистики (2-е изд.). Oxford University Press. doi : 10.1093/acref/9780195139778.001.0001. ISBN 9780195139778.