Индексированный язык

Индексированные языки — это класс формальных языков, открытый Альфредом Ахо ; ^[1] они описываются индексированными грамматиками и могут распознаваться вложенными стековыми автоматами . ^[2]

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

Класс индексированных языков имеет практическое значение в обработке естественного языка как доступный в вычислительном отношении метод. ^{[ нужна ссылка ]} обобщение контекстно-свободных языков , поскольку индексированные грамматики могут описывать многие нелокальные ограничения, возникающие в естественных языках.

Джеральд Газдар (1988) ^[3] и Виджай-Шанкер (1987) ^[4] представил слегка контекстно-зависимый языковой класс, теперь известный как линейно-индексированные грамматики (LIG). ^[5] Линейно-индексированные грамматики имеют дополнительные ограничения относительно IG. LIG слабо эквивалентны (генерируют тот же языковой класс), что и грамматики, примыкающие к дереву . ^[6]

Примеры [ править ]

Следующие языки индексируются, но не являются контекстно-свободными:

\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}

^[3]

\{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}

^[2]

Эти два языка также индексируются, но, согласно характеристике Газдара, они не являются даже в некоторой степени контекстно-зависимыми:

\{a^{2^{n}}|n\geq 0\}

^[2]

\{www|w\in \{a,b\}^{+}\}

^[3]

С другой стороны, следующий язык не индексируется: ^[7]

\{(ab^{n})^{n}|n\geq 0\}

Свойства [ править ]

Хопкрофт и Ульман склонны рассматривать индексированные языки как «естественный» класс, поскольку они порождены несколькими формализмами, такими как: ^[9]

Ахо Индексированные грамматики ^[1]
Автоматы Ахо с односторонним вложенным стеком ^[10]
Фишера Макрограмматики ^[11]
Автоматы Грайбаха со стопками стопок ^[12]
Майбаума Алгебраическая характеристика ^[13]

Хаяши ^[14] обобщил лемму о накачке на индексированные грамматики.И наоборот, Гилман ^[7] дает «лемму о сокращении» для индексируемых языков.

См. также [ править ]

Иерархия Хомского

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д Ахо, Альфред (1968). «Индексированные грамматики — расширение контекстно-свободных грамматик» . Журнал АКМ . 15 (4): 647–671. дои : 10.1145/321479.321488 . S2CID 9539666 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Парти, Барбара ; тер Мейлен, Алиса ; Уолл, Роберт Э. (1990). Математические методы в лингвистике . Академическое издательство Клювер. стр. 536–542. ISBN 978-90-277-2245-4 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». Ин Рейл, Ю.; Рорер, К. (ред.). Синтаксический анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. Спрингер Нидерланды. стр. 69–94. дои : 10.1007/978-94-009-1337-0_3 . ISBN 978-94-009-1337-0 .
^ Виджаяшанкер, К. (1987). Исследование древовидных грамматик (Диссертация). ПроКвест 303610666 .
^ Калмейер, Лаура (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Спрингер. п. 31. ISBN 978-3-642-14846-0 .
^ Калмейер, Лаура (16 августа 2010 г.). Синтаксический анализ за пределами контекстно-свободных грамматик . Спрингер. п. 32. ISBN 978-3-642-14846-0 .
↑ Перейти обратно: Перейти обратно: ^а ^б Гилман, Роберт Х. (1996). «Сжимающая лемма для индексируемых языков». Теоретическая информатика . 163 (1–2): 277–281. arXiv : математика/9509205 . дои : 10.1016/0304-3975(96)00244-7 . S2CID 14479068 .
^ Хопкрофт, Джон ; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. п. 390. ИСБН 978-0-201-02988-8 .
^ Введение в теорию автоматов, языки и вычисления, ^[8] Библиографические примечания, стр.394-395.
^ Ахо, Альфред В. (июль 1969 г.). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .
^ Фишер, Майкл Дж. (октябрь 1968 г.). «Грамматики с макроподобными постановками». 9-й ежегодный симпозиум по теории коммутации и автоматов (Сват, 1968) . 9-й ежегодный симпозиум по теории коммутации и автоматов (1968 г.). стр. 131–142. дои : 10.1109/SWAT.1968.12 .
^ Грейбах, Шейла А. (март 1970 г.). «Полные AFL и вложенная итерационная замена». Информация и контроль . 16 (1): 7–35. дои : 10.1016/s0019-9958(70)80039-0 .
^ Майбаум, TSE (июнь 1974 г.). «Обобщенный подход к формальным языкам» . Журнал компьютерных и системных наук . 8 (3): 409–439. дои : 10.1016/s0022-0000(74)80031-0 .
^ Хаяси, Такеши (1973). «О деревьях вывода индексированных грамматик: расширение {$uvwxy$}-теоремы» . Публикации НИИ математических наук . 9 (1): 61–92. дои : 10.2977/prims/1195192738 .

Внешние ссылки [ править ]

Глава «НЛП в Прологе», посвященная индексированным грамматикам и языкам.

[aho1968-1] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Ахо, Альфред (1968). «Индексированные грамматики — расширение контекстно-свободных грамматик» . Журнал АКМ . 15 (4): 647–671. дои : 10.1145/321479.321488 . S2CID 9539666 .

[partee_etal_1990-2] Перейти обратно: Перейти обратно: ^а ^б ^с Парти, Барбара ; тер Мейлен, Алиса ; Уолл, Роберт Э. (1990). Математические методы в лингвистике . Академическое издательство Клювер. стр. 536–542. ISBN 978-90-277-2245-4 .

[gazdar1998-3] Перейти обратно: Перейти обратно: ^а ^б ^с Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». Ин Рейл, Ю.; Рорер, К. (ред.). Синтаксический анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. Спрингер Нидерланды. стр. 69–94. дои : 10.1007/978-94-009-1337-0_3 . ISBN 978-94-009-1337-0 .

[4] Виджаяшанкер, К. (1987). Исследование древовидных грамматик (Диссертация). ПроКвест 303610666 .

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

[Kallmeyer2010b-6] Калмейер, Лаура (16 августа 2010 г.). Синтаксический анализ за пределами контекстно-свободных грамматик . Спрингер. п. 32. ISBN 978-3-642-14846-0 .

[Gilman.1996-7] Перейти обратно: Перейти обратно: ^а ^б Гилман, Роберт Х. (1996). «Сжимающая лемма для индексируемых языков». Теоретическая информатика . 163 (1–2): 277–281. arXiv : математика/9509205 . дои : 10.1016/0304-3975(96)00244-7 . S2CID 14479068 .

[hopcroft_ullman_1979-8] Хопкрофт, Джон ; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. п. 390. ИСБН 978-0-201-02988-8 .

[9] Введение в теорию автоматов, языки и вычисления, ^[8] Библиографические примечания, стр.394-395.

[10] Ахо, Альфред В. (июль 1969 г.). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .

[11] Фишер, Майкл Дж. (октябрь 1968 г.). «Грамматики с макроподобными постановками». 9-й ежегодный симпозиум по теории коммутации и автоматов (Сват, 1968) . 9-й ежегодный симпозиум по теории коммутации и автоматов (1968 г.). стр. 131–142. дои : 10.1109/SWAT.1968.12 .

[12] Грейбах, Шейла А. (март 1970 г.). «Полные AFL и вложенная итерационная замена». Информация и контроль . 16 (1): 7–35. дои : 10.1016/s0019-9958(70)80039-0 .

[13] Майбаум, TSE (июнь 1974 г.). «Обобщенный подход к формальным языкам» . Журнал компьютерных и системных наук . 8 (3): 409–439. дои : 10.1016/s0022-0000(74)80031-0 .

[14] Хаяси, Такеши (1973). «О деревьях вывода индексированных грамматик: расширение {$uvwxy$}-теоремы» . Публикации НИИ математических наук . 9 (1): 61–92. дои : 10.2977/prims/1195192738 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

[12]

[13]

[14]

[8]