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

• Определение индексированных языков

  • Индексированные языки — класс формальных языков, открытых Альфредом Ахо. 
  • Описываются индексированными грамматиками и распознаются автоматами с вложенным стеком. 

• Связь с контекстно-зависимыми языками

  • Являются подмножеством контекстно-зависимых языков. 
  • Удовлетворяют многим свойствам замыкания, но не замкнуты при пересечении или дополнении. 

• Практическое значение

  • Важны для обработки естественного языка, обобщая контекстно-свободные языки. 

• Линейные индексированные грамматики

  • Представлены Джеральдом Газдаром и Виджай-Шанкером. 
  • Имеют дополнительные ограничения по сравнению с IG. 
  • Слабо эквивалентны древовидным грамматикам. 

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

  • Некоторые языки индексируются, но не являются контекстно-свободными. 
  • Другие языки индексируются, но слабо зависят от контекста. 
  • Один язык не индексируется. 

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

  • Хопкрофт и Ульман считают их «естественным» классом, поскольку они генерируются различными формализмами. 
  • Гилман предлагает «сокращающуюся лемму» для индексированных языков. 

• Дополнительные сведения

  • Упоминается иерархия Хомского и глава о НЛП в прологе, посвященная индексированным грамматикам и языкам.