Иерархия Хомского — классификация формальных языков и формальных грамматик , согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института , лингвистом Ноамом Хомским .

Классификация грамматик

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

Тип 0 — неограниченные

Грамматика с фразовой структурой G — это алгебраическая структура , упорядоченная четвёрка (V _T , V _N , P, S), где :

• ${\displaystyle V_{T}}$ — алфавит (множество) терминальных символов — терминалов ,
• ${\displaystyle V_{N}}$ — алфавит (множество) нетерминальных символов — нетерминалов ,
• ${\displaystyle V=V_{T}\cup V_{N}}$ — словарь ${\displaystyle G}$ , причём ${\displaystyle V_{T}\cap V_{N}=\varnothing }$
• ${\displaystyle P}$ — конечное множество продукций (правил) грамматики, ${\displaystyle P\subseteq V^{+}\times V^{*}}$
• ${\displaystyle S}$ — начальный символ ( источник ).

Здесь ${\displaystyle V^{*}}$ — множество всех строк над алфавитом ${\displaystyle V}$ , а ${\displaystyle V^{+}}$ — множество непустых строк над алфавитом ${\displaystyle V}$ .

К типу 0 по классификации Хомского относятся — грамматики с фразовой структурой , то есть все без исключения формальные грамматики. Правила можно записать в виде:

${\displaystyle \alpha \rightarrow \beta }$ ,

где ${\displaystyle \alpha \in V^{+}}$ — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а ${\displaystyle \beta \in V^{*}}$ — любая цепочка символов из алфавита.

Практического применения в силу своей сложности такие грамматики не имеют.

Тип 1 — контекстно-зависимые

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики ${\displaystyle G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}}$ все правила имеют вид :

• ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ , где ${\displaystyle \alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}}$ . Такие грамматики относят к контекстно-зависимым.
• ${\displaystyle \alpha \rightarrow \beta }$ , где ${\displaystyle \alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |}$ . Такие грамматики относят к неукорачивающим.

Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.

Тип 2 — контекстно-свободные

К этому типу относятся контекстно-свободные (КС) грамматики . Для грамматики ${\displaystyle G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}}$ все правила имеют вид:

• ${\displaystyle A\rightarrow \beta }$ , где ${\displaystyle \beta \in V^{+}}$ (для неукорачивающих КС-грамматик) или ${\displaystyle \beta \in V^{*}}$ (для укорачивающих), ${\displaystyle A\in V_{N}}$ . То есть грамматика допускает появление в левой части правила только .

КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. синтаксический анализ ).

Тип 3 — регулярные

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

Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:

• ${\displaystyle A\rightarrow B\gamma }$ или ${\displaystyle A\rightarrow \gamma }$ , где ${\displaystyle \gamma \in V_{T}^{*},A,B\in V_{N}}$ (для леволинейных грамматик).
• ${\displaystyle A\rightarrow \gamma B}$ ; или ${\displaystyle A\rightarrow \gamma }$ , где ${\displaystyle \gamma \in V_{T}^{*},A,B\in V_{N}}$ (для праволинейных грамматик).

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

Классификация языков

Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.

Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.

Примечания

Литература

• Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 2006.
• Джон Хопкрофт , Раджив Мотвани , Джеффри Ульман . ГЛАВА 5. Контекстно-свободные грамматики и языки // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М. : , 2002. — С. 528. — ISBN 0-201-44124-1 .
• Серебряков В. А. , Галочкин М. П., Гончар Д. Р., Фуругян М. Г. — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
• . Основные концепции компиляторов = The Essence of Compilers. — М. : , 2002. — С. 256. — ISBN 5-8459-0360-2 .
• Кук Д., Бейз Г. Глава 8. Языки и грамматики // Компьютерная математика = Computer Mathematics. — М. : Наука. Физматлит, 1990. — 384 с. — ISBN 5-02-014216-6 .