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

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

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

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

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

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

• <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 = \empty</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</math> — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а <math>\beta</math> — любая цепочка символов из алфавита.

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

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

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

• <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

Литература

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

Отрывок, характеризующий Иерархия Хомского

«Ну, еще, еще наддай!» – обращался он мысленно к этим звукам и опять пускался скакать по линии, всё дальше и дальше проникая в область войск, уже вступивших в дело.
«Уж как это там будет, не знаю, а всё будет хорошо!» думал Ростов.
Проехав какие то австрийские войска, Ростов заметил, что следующая за тем часть линии (это была гвардия) уже вступила в дело.
«Тем лучше! посмотрю вблизи», подумал он.
Он поехал почти по передней линии. Несколько всадников скакали по направлению к нему. Это были наши лейб уланы, которые расстроенными рядами возвращались из атаки. Ростов миновал их, заметил невольно одного из них в крови и поскакал дальше.
«Мне до этого дела нет!» подумал он. Не успел он проехать нескольких сот шагов после этого, как влево от него, наперерез ему, показалась на всем протяжении поля огромная масса кавалеристов на вороных лошадях, в белых блестящих мундирах, которые рысью шли прямо на него. Ростов пустил лошадь во весь скок, для того чтоб уехать с дороги от этих кавалеристов, и он бы уехал от них, ежели бы они шли всё тем же аллюром, но они всё прибавляли хода, так что некоторые лошади уже скакали. Ростову всё слышнее и слышнее становился их топот и бряцание их оружия и виднее становились их лошади, фигуры и даже лица. Это были наши кавалергарды, шедшие в атаку на французскую кавалерию, подвигавшуюся им навстречу.
Кавалергарды скакали, но еще удерживая лошадей. Ростов уже видел их лица и услышал команду: «марш, марш!» произнесенную офицером, выпустившим во весь мах свою кровную лошадь. Ростов, опасаясь быть раздавленным или завлеченным в атаку на французов, скакал вдоль фронта, что было мочи у его лошади, и всё таки не успел миновать их.
Крайний кавалергард, огромный ростом рябой мужчина, злобно нахмурился, увидав перед собой Ростова, с которым он неминуемо должен был столкнуться. Этот кавалергард непременно сбил бы с ног Ростова с его Бедуином (Ростов сам себе казался таким маленьким и слабеньким в сравнении с этими громадными людьми и лошадьми), ежели бы он не догадался взмахнуть нагайкой в глаза кавалергардовой лошади. Вороная, тяжелая, пятивершковая лошадь шарахнулась, приложив уши; но рябой кавалергард всадил ей с размаху в бока огромные шпоры, и лошадь, взмахнув хвостом и вытянув шею, понеслась еще быстрее. Едва кавалергарды миновали Ростова, как он услыхал их крик: «Ура!» и оглянувшись увидал, что передние ряды их смешивались с чужими, вероятно французскими, кавалеристами в красных эполетах. Дальше нельзя было ничего видеть, потому что тотчас же после этого откуда то стали стрелять пушки, и всё застлалось дымом.
В ту минуту как кавалергарды, миновав его, скрылись в дыму, Ростов колебался, скакать ли ему за ними или ехать туда, куда ему нужно было. Это была та блестящая атака кавалергардов, которой удивлялись сами французы. Ростову страшно было слышать потом, что из всей этой массы огромных красавцев людей, из всех этих блестящих, на тысячных лошадях, богачей юношей, офицеров и юнкеров, проскакавших мимо его, после атаки осталось только осьмнадцать человек.
«Что мне завидовать, мое не уйдет, и я сейчас, может быть, увижу государя!» подумал Ростов и поскакал дальше.
Поровнявшись с гвардейской пехотой, он заметил, что чрез нее и около нее летали ядры, не столько потому, что он слышал звук ядер, сколько потому, что на лицах солдат он увидал беспокойство и на лицах офицеров – неестественную, воинственную торжественность.
Проезжая позади одной из линий пехотных гвардейских полков, он услыхал голос, назвавший его по имени.
– Ростов!
– Что? – откликнулся он, не узнавая Бориса.
– Каково? в первую линию попали! Наш полк в атаку ходил! – сказал Борис, улыбаясь той счастливой улыбкой, которая бывает у молодых людей, в первый раз побывавших в огне.
Ростов остановился.
– Вот как! – сказал он. – Ну что?
– Отбили! – оживленно сказал Борис, сделавшийся болтливым. – Ты можешь себе представить?
И Борис стал рассказывать, каким образом гвардия, ставши на место и увидав перед собой войска, приняла их за австрийцев и вдруг по ядрам, пущенным из этих войск, узнала, что она в первой линии, и неожиданно должна была вступить в дело. Ростов, не дослушав Бориса, тронул свою лошадь.
– Ты куда? – спросил Борис.
– К его величеству с поручением.
– Вот он! – сказал Борис, которому послышалось, что Ростову нужно было его высочество, вместо его величества.
И он указал ему на великого князя, который в ста шагах от них, в каске и в кавалергардском колете, с своими поднятыми плечами и нахмуренными бровями, что то кричал австрийскому белому и бледному офицеру.
– Да ведь это великий князь, а мне к главнокомандующему или к государю, – сказал Ростов и тронул было лошадь.
– Граф, граф! – кричал Берг, такой же оживленный, как и Борис, подбегая с другой стороны, – граф, я в правую руку ранен (говорил он, показывая кисть руки, окровавленную, обвязанную носовым платком) и остался во фронте. Граф, держу шпагу в левой руке: в нашей породе фон Бергов, граф, все были рыцари.
Берг еще что то говорил, но Ростов, не дослушав его, уже поехал дальше.
Проехав гвардию и пустой промежуток, Ростов, для того чтобы не попасть опять в первую линию, как он попал под атаку кавалергардов, поехал по линии резервов, далеко объезжая то место, где слышалась самая жаркая стрельба и канонада. Вдруг впереди себя и позади наших войск, в таком месте, где он никак не мог предполагать неприятеля, он услыхал близкую ружейную стрельбу.