Иерархия Хомского
Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачуссетского технологического института, лингвистом Ноамом Хомским.
Классификация грамматик
Согласно Хомскому, формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.
Тип 0 — неограниченные
К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это — все без исключения формальные грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:
- <math>\alpha\rarr\beta</math>, где <math>\alpha</math> — любая цепочка, содержащая хотя бы один нетерминальный символ, а <math>\beta</math> — любая цепочка символов из алфавита.
Практического применения в силу своей сложности такие грамматики не имеют.
Тип 1 — контекстно-зависимые
К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:
- αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN. Такие грамматики относят к контекстно-зависимым.
- α→β, где α, β∈V+, |α|≤|β|. Такие грамматики относят к неукорачивающим.
Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности.
Тип 2 — контекстно-свободные
К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:
- A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈VN. То есть грамматика допускает появление в левой части правила только нетерминального символа.
КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. грамматический анализ).
Тип 3 — регулярные
К третьему типу относятся регулярные грамматики — самые простые из формальных грамматик. Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:
- A→Bγ или A→γ, где γ∈VT*, A, B∈VN (для леволинейных грамматик).
- A→γB; или A→γ, где γ∈VT*, A, B∈VN (для праволинейных грамматик).
Регулярные грамматики применяются для описания простейших конструкций: идентификаторов, строк, констант, а также языков ассемблера, командных процессоров и др.
Классификация языков
Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.
Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.
Источники
- А.Ю. Молчанов. Системное программное обеспечение. Санкт-Петербург. Питер, 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
af:Chomsky-hiërargie bg:Йерархия на Чомски bn:চম্স্কি স্তরক্রম bs:Chomskyjeva hijerarhija ca:Jerarquia de Chomsky cs:Chomského hierarchie de:Chomsky-Hierarchie en:Chomsky hierarchy es:Jerarquía de Chomsky fa:وراثت چامسکى fi:Chomskyn hierarkia fr:Hiérarchie de Chomsky hr:Chomskyjeva hijerarhija it:Gerarchia di Chomsky ja:チョムスキー階層 ko:촘스키 위계 mk:Хиерархија на Чомски nl:Chomskyhiërarchie nn:Chomskyhierarkiet no:Chomskyhierarkiet pl:Hierarchia Chomsky'ego pt:Hierarquia de Chomsky ro:Ierarhia Chomsky sh:Chomskyjeva hijerarhija sk:Chomského hierarchia sr:Hijerarhija Čomskog zh:乔姆斯基谱系
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....