Межсерийные зависимости

В лингвистике межсерийные зависимости также называют перекрестными зависимостями) ( некоторые авторы ^[1]) возникает, когда линии, представляющие отношения зависимости между двумя сериями слов, пересекаются друг с другом. ^[2] Они представляют особый интерес для лингвистов, желающих определить синтаксическую структуру естественного языка; языки, содержащие произвольное их количество, не являются контекстно-свободными . Этим фактом голландцы ^[3] и швейцарско-немецкий ^[4] было доказано, что они не являются контекстно-свободными.

Пример

Швейцарско-немецкое предложение, содержащее перекрестные зависимости (показаны линиями между глаголами и их объектами). Для сравнения показан английский перевод с непересекающимися зависимостями.

Более сложный пример.

Поскольку швейцарско-немецкий язык позволяет упорядочивать глаголы и их аргументы в перекрестном порядке, у нас есть следующий пример, взятый из Шибера: ^[4]

... более	в Гансе	является	дом	отклонения	Австрия.
... мы	Его ( что )	тот	дом ( соотв )	помощь	краска.

То есть «мы помогаем Гансу покрасить дом».

Обратите внимание, что последовательные именные группы em Hans ( Ганс ) и es huus ( дом ), а также последовательные глаголы hälfed ( помощь ) и aastriiche ( красить ) образуют две отдельные серии составляющих. Обратите также внимание, что дательный глагол hälfed и винительный глагол aastriiche дательный падеж em Hans и винительный падеж es huus принимают в качестве аргументов соответственно.

Неконтекстная свобода

Позволять $L_{SG}$ быть набором всех швейцарско-немецких предложений. Мы докажем математически, что $L_{SG}$ не является контекстно-свободным.

В швейцарско-немецких предложениях количество глаголов грамматического падежа (дательного или винительного) должно соответствовать количеству объектов этого падежа. Кроме того, допустимо (в принципе) предложение, содержащее произвольное количество таких объектов. Следовательно, мы можем определить следующий формальный язык , подмножество $L_{SG}$ : $L={\text{De Jan}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer}}{\text{ (d'chind)}}{}^{m}{\text{ (em}}{\text{ Hans)}}{}^{n}{\text{ s}}{\text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{m}{\text{ (h}}{\ddot {\mathrm {a} }}{\text{lfe)}}{}^{n}{\text{ aastriiche.}}$ Таким образом, мы имеем $L=L_{SG}\cap L_{r}$ , где $L_{r}$ является регулярным языком, определяемым $L={\text{De Jan}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer}}{\text{ (d'chind)}}{}^{+}{\text{ (em}}{\text{ Hans)}}{}^{+}{\text{ s}}{\text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{+}{\text{ (h}}{\ddot {\mathrm {a} }}{\text{lfe)}}{}^{+}{\text{ aastriiche.}}$ где верхний индекс плюс означает «одна или несколько копий». Поскольку множество контекстно-свободных языков замкнуто относительно пересечения с регулярными языками, нам нужно лишь доказать, что $L$ не является контекстно-свободным (, ^[5] стр. 130–135).

После замены слов $L$ имеет форму $\{xa^{m}b^{n}yc^{m}d^{n}z|m,n\geq 1\}$ . С $L$ может быть сопоставлен с $L'$ по следующей карте: $x,y,z\mapsto \epsilon ;a\mapsto a;b\mapsto b;c\mapsto c$ , и поскольку контекстно-свободные языки замкнуты относительно отображений терминальных символов в терминальные строки (т. е. гомоморфизма ) (, ^[5] стр. 130–135), нам нужно лишь доказать, что $L'$ не является контекстно-свободным.

$L'=\{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}$ — стандартный пример неконтекстно-свободного языка (, ^[5] п. 128). Это можно показать с помощью леммы Огдена .

Предположим, что язык порождается контекстно-свободной грамматикой, тогда пусть $p$ — длина, требуемая в лемме Огдена, затем рассмотрим слово $a^{p}b^{p}c^{p}d^{p}$ на языке и отметьте буквы $b^{p}c^{p}$ . Тогда три условия, подразумеваемые леммой Огдена, не могут быть удовлетворены все.

Аналогичным образом можно доказать, что все известные разговорные языки, содержащие межпоследовательные зависимости, не являются контекстно-свободными. ^[2] Это привело к отказу от грамматики обобщенной фразовой структуры после того, как в 1980-х годах в естественных языках были выявлены перекрестные зависимости. ^[6]

Уход

Исследования слабо контекстно-зависимых языков попытались определить более узкий и более вычислительно управляемый подкласс контекстно-зависимых языков , который может улавливать контекстно-зависимую чувствительность, как в естественных языках. Например, межпоследовательные зависимости могут быть выражены в линейных системах контекстно-свободной перезаписи (LCFRS); можно написать грамматику LCFRS для { a ^нб ^нс ^нд ^н | n ≥ 1}, например. ^[7]^[8]^[9]

Ссылки

^ Стейблер, Эдвард (2004), «Разновидности перекрестных зависимостей: структурная зависимость и умеренная контекстная чувствительность» (PDF) , Cognitive Science , 28 (5): 699–720, doi : 10.1016/j.cogsci.2004.05.002 .
^ Jump up to: ^а ^б Юрафский, Дэниел; Мартин, Джеймс Х. (2000). Обработка речи и языка (1-е изд.). Прентис Холл. стр. 473–495. ISBN 978-0-13-095069-7 . .
^ Бреснан, Джоан; М. Каплан, Рональд (1982), «Перекрестные зависимости в голландском языке», Linguistic Inquiry , 13 (4): 613–635 .
^ Jump up to: ^а ^б Шибер, Стюарт (1985), «Свидетельства против контекстной свободы естественного языка» (PDF) , Linguistics and Philosophy , 8 (3): 333–343, doi : 10.1007/BF00630917 , S2CID 222277837 .
^ Jump up to: ^а ^б ^с Джон Э. Хопкрофт , Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Пирсон Образование. ISBN 978-0-201-44124-6 . .
^ Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». Синтаксический анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. С. 69–94. дои : 10.1007/978-94-009-1337-0_3 . ISBN 978-1-55608-056-2 .
^ http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4nl-cfg.pdf ^{[ пустой URL PDF ]}
^ http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4lcfrs-intro.pdf ^{[ пустой URL PDF ]}
^ Лаура Каллмейер (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 1–5. ISBN 978-3-642-14846-0 .

[stabler2004-1] Стейблер, Эдвард (2004), «Разновидности перекрестных зависимостей: структурная зависимость и умеренная контекстная чувствительность» (PDF) , Cognitive Science , 28 (5): 699–720, doi : 10.1016/j.cogsci.2004.05.002 .

[jurafsky2000-2] Jump up to: ^а ^б Юрафский, Дэниел; Мартин, Джеймс Х. (2000). Обработка речи и языка (1-е изд.). Прентис Холл. стр. 473–495. ISBN 978-0-13-095069-7 . .

[bresnan1982-3] Бреснан, Джоан; М. Каплан, Рональд (1982), «Перекрестные зависимости в голландском языке», Linguistic Inquiry , 13 (4): 613–635 .

[shieber1985-4] Jump up to: ^а ^б Шибер, Стюарт (1985), «Свидетельства против контекстной свободы естественного языка» (PDF) , Linguistics and Philosophy , 8 (3): 333–343, doi : 10.1007/BF00630917 , S2CID 222277837 .

[hopcroft2000-5] Jump up to: ^а ^б ^с Джон Э. Хопкрофт , Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Пирсон Образование. ISBN 978-0-201-44124-6 . .

[6] Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». Синтаксический анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. С. 69–94. дои : 10.1007/978-94-009-1337-0_3 . ISBN 978-1-55608-056-2 .

[7] ttp://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4nl-cfg.pdf ^{[ пустой URL PDF ]}

[8] ttp://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4lcfrs-intro.pdf ^{[ пустой URL PDF ]}

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]