Оглавление
- 1 Контекстно-зависимая грамматика
- 1.1 Определение и свойства контекстно-зависимых грамматик
- 1.2 Примеры и грамматика для {a2i | i ≥ 1}
- 1.3 Нормальная форма Куроды и эквивалентность линейному ограниченному автомату
- 1.4 Свойства закрытия и вычислительные задачи
- 1.5 Применение CSGs в моделировании естественных языков
- 1.6 Иерархия Хомского и дальнейшие исследования
- 2 Контекстно-зависимая грамматика — Википедия
Контекстно-зависимая грамматика
-
Определение и свойства контекстно-зависимых грамматик
- Контекстно-зависимые грамматики (CSGs) – это формальные языки, которые могут быть описаны с помощью контекстно-зависимых правил.
- Они отличаются от контекстно-свободных грамматик (CSGs) тем, что могут иметь правила, зависящие от контекста.
- CSGs могут быть использованы для описания языков, которые не являются регулярными, но не являются и рекурсивными.
-
Примеры и грамматика для {a2i | i ≥ 1}
- Приведен пример грамматики для языка {a2i | i ≥ 1}, который включает правила для генерации строк с повторениями.
- Грамматика включает правила для генерации различных подстрок, таких как a, aa, aaa, и т.д.
-
Нормальная форма Куроды и эквивалентность линейному ограниченному автомату
- CSGs могут быть преобразованы в слабо эквивалентные грамматики в нормальной форме Куроды.
- Линейные ограниченные автоматы (LBA) могут принимать только контекстно-зависимые языки.
- Вопрос о том, каждый ли контекстно-зависимый язык может быть принят детерминированным LBA, остается открытым.
-
Свойства закрытия и вычислительные задачи
- Контекстно-зависимые языки замкнуты в различных операциях, включая дополнение, объединение, пересечение и другие.
- Задача решения принадлежности строки к контекстно-зависимой грамматике является PSPACE-полной.
- Проблема пустоты для контекстно-зависимых грамматик неразрешима.
-
Применение CSGs в моделировании естественных языков
- Савич критикует CSGs как основу для моделирования естественных языков из-за их PSPACE-полноты.
- Некоторые естественные языки могут быть описаны CSGs, но класс CSG в целом считается слишком большим для практического использования.
- Существуют другие классы языков, которые могут учитывать контекстную чувствительность, такие как LCFRSs и PTIME.
-
Иерархия Хомского и дальнейшие исследования
- CSGs находятся между контекстно-свободными и рекурсивными языками в иерархии Хомского.
- Современные исследования в компьютерной лингвистике направлены на разработку языков, которые находятся между контекстно-свободными и контекстно-зависимыми, и на решение задач, связанных с этими языками.
Полный текст статьи: