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

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

Definition

Иерархия Хомского — это классификация формальных грамматик по прогрессивно усиливающимся ограничениям на их правила вывода, что приводит к классам регулярных, контекстно-свободных, контекстно-зависимых и рекурсивно перечислимых языков в цепочке строгих включений.

Scope

Эта тема охватывает четыре типа грамматик — неограниченные, контекстно-зависимые, контекстно-свободные и регулярные — их строгое включение, а также модель автомата, соответствующую каждому уровню, а именно машину Тьюринга, линейно-ограниченный автомат, автомат с магазинной памятью и конечный автомат, наряду со свойствами замыкания и разрешимости, которые разделяют эти уровни.

Core questions

• Как ограничения на правила грамматики преобразуются в ограничения на память и вычислительную мощность?
• Почему каждый уровень иерархии строго содержится в следующем?
• Какая модель автомата соответствует каждому типу грамматики?
• Как изменяются свойства разрешимости и замыкания при переходе вверх по иерархии?

Key theories

Соответствие грамматика–машина

Каждый класс грамматик распознаётся определённой моделью машины — регулярные конечными автоматами, контекстно-свободные автоматами с магазинной памятью, контекстно-зависимые линейно-ограниченными автоматами, а неограниченные машинами Тьюринга — связывая генеративные и операционные описания вычислений.

Строгое включение классов языков

Каждый уровень правильно содержит предыдущий, что подтверждается конкретными разделяющими языками, поэтому иерархия представляет собой подлинную лестницу возрастающей выразительной мощности, а не набор эквивалентных описаний.

Clinical relevance

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

History

Хомский предложил иерархию в конце 1950-х годов, стремясь найти формальные модели синтаксиса естественного языка, а соответствия машинам были установлены по мере развития теории автоматов в 1960-х годах, причём линейно-ограниченные автоматы были введены Майхиллом, а контекстно-зависимый уровень был уточнён Куродой.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Каковы четыре уровня иерархии Хомского?

От наименее к наиболее мощным они включают регулярные языки (Тип 3), контекстно-свободные языки (Тип 2), контекстно-зависимые языки (Тип 1) и рекурсивно перечислимые языки (Тип 0). Каждый уровень ослабляет ограничения на правила грамматики и соответствует машине с большей памятью.

Охватывается ли естественный язык иерархией Хомского?

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