Контекстно-зависимая грамматика

• Определение и свойства контекстно-зависимых грамматик

  • Контекстно-зависимые грамматики (CSGs) — это формальные языки, которые могут быть описаны с помощью контекстно-зависимых правил. 
  • Они отличаются от контекстно-свободных грамматик (CSGs) тем, что могут иметь правила, зависящие от контекста. 
  • CSGs могут быть использованы для описания языков, которые не являются регулярными, но не являются и рекурсивными. 

• Примеры и грамматика для {a2i | i ≥ 1}

  • Приведен пример грамматики для языка {a2i | i ≥ 1}, который включает правила для генерации строк с повторениями. 
  • Грамматика включает правила для генерации различных подстрок, таких как a, aa, aaa, и т.д. 

• Нормальная форма Куроды и эквивалентность линейному ограниченному автомату

  • CSGs могут быть преобразованы в слабо эквивалентные грамматики в нормальной форме Куроды. 
  • Линейные ограниченные автоматы (LBA) могут принимать только контекстно-зависимые языки. 
  • Вопрос о том, каждый ли контекстно-зависимый язык может быть принят детерминированным LBA, остается открытым. 

• Свойства закрытия и вычислительные задачи

  • Контекстно-зависимые языки замкнуты в различных операциях, включая дополнение, объединение, пересечение и другие. 
  • Задача решения принадлежности строки к контекстно-зависимой грамматике является PSPACE-полной. 
  • Проблема пустоты для контекстно-зависимых грамматик неразрешима. 

• Применение CSGs в моделировании естественных языков

  • Савич критикует CSGs как основу для моделирования естественных языков из-за их PSPACE-полноты. 
  • Некоторые естественные языки могут быть описаны CSGs, но класс CSG в целом считается слишком большим для практического использования. 
  • Существуют другие классы языков, которые могут учитывать контекстную чувствительность, такие как LCFRSs и PTIME. 

• Иерархия Хомского и дальнейшие исследования

  • CSGs находятся между контекстно-свободными и рекурсивными языками в иерархии Хомского. 
  • Современные исследования в компьютерной лингвистике направлены на разработку языков, которые находятся между контекстно-свободными и контекстно-зависимыми, и на решение задач, связанных с этими языками.