Русская Википедия:Иерархия Хомского

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

• <math>V_T</math> — алфавит (множество) терминальных символов — терминалов,
• <math>V_N</math> — алфавит (множество) нетерминальных символов — нетерминалов,
• <math>V = V_T \cup V_N</math> — словарь <math>G</math>, причём <math>V_T \cap V_N = \varnothing</math>
• <math>P</math> — конечное множество продукций (правил) грамматики, <math>P \subseteq V^+\times V^*</math>
• <math>S</math> — начальный символ (источник).

Здесь <math>V^*</math> — множество всех строк над алфавитом <math>V</math>, а <math>V^+</math> — множество непустых строк над алфавитом <math>V</math>.

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

<math>\alpha\rarr\beta</math>,

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

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

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

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики <math>G(V_T,V_N, P, S), V=V_T \cup V_N</math> все правила имеют видШаблон:Sfn:

• <math>\alpha A \beta \rarr \alpha \gamma \beta</math>, где <math>\alpha, \beta \in V^*, \gamma \in V^+, A \in V_N</math>. Такие грамматики относят к контекстно-зависимым.
• <math>\alpha \rarr \beta</math>, где <math>\alpha, \beta \in V^+, 1\le|\alpha|\le|\beta|</math>. Такие грамматики относят к неукорачивающим.

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

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

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики <math>G(V_T,V_N,P, S), V=V_T \cup V_N</math> все правила имеют вид:

• <math>A \rarr \beta</math>, где <math>\beta \in V^+</math> (для неукорачивающих КС-грамматик) или <math>\beta \in V^*</math> (для укорачивающих), <math>A \in V_N</math>. То есть грамматика допускает появление в левой части правила только нетерминального символа.

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

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

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

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

• <math>A \rarr B\gamma</math> или <math>A \rarr \gamma</math>, где <math>\gamma \in V_T^*, A, B \in V_N</math> (для леволинейных грамматик).
• <math>A \rarr \gamma B</math>; или <math>A \rarr \gamma</math>, где <math>\gamma \in V_T^*, A, B \in V_N</math> (для праволинейных грамматик).

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

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

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

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

Литература

• Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 2006.
• Шаблон:Книга
• Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
• Шаблон:Книга
• Шаблон:Книга