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

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

  • Иерархия Хомского описывает классы формальных грамматик в теории формальных языков. 
  • Ноам Хомский предложил четыре класса грамматик, каждый из которых генерирует более сложные языки. 
  • Каждый класс может полностью генерировать языки младших классов. 

• История и развитие

  • Общая идея иерархии была впервые описана Хомским в книге «Три модели описания языка». 
  • Марсель-Пол Шютценбергер внес вклад в развитие теории формальных языков. 
  • Математики также разрабатывали модели вычислений, которые оказались эквивалентными грамматикам Хомского. 

• Классы грамматик

  • Обычные грамматики генерируют обычные языки и ограничены одним нетерминалом и одним терминалом в правилах. 
  • Контекстно-свободные грамматики генерируют контекстно-свободные языки и распознаются недетерминированными автоматами pushdown. 
  • Контекстно-зависимые грамматики генерируют контекстно-зависимые языки и распознаются линейными ограниченными автоматами. 
  • Рекурсивно перечислимые грамматики генерируют все языки, которые могут быть распознаны машиной Тьюринга. 

• Примеры и приложения

  • Примеры языков, генерируемых грамматиками разных типов, включают регулярные выражения и языки программирования. 
  • Контекстно-зависимые языки используются в синтаксическом анализе языков программирования. 

• Нормальная форма Хомского

  • Нормальная форма Хомского представляет собой упрощенную форму грамматики, которая используется для доказательства свойств грамматик.