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



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

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

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

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

К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это — все без исключения формальные грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:

  • , где α — любая цепочка, содержащая хотя бы один нетерминальный символ, а β — любая цепочки символов из алфавита.

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

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

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:

  • αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN. Такие грамматики относят к контекстно-зависимым.

  • α→β, где α, β∈V+, |α|<|β|. Такие грамматики относят к неукорачивающим.

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

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

К этому типу относятся org/wiki/контекстно-свободные">контекстно-свободные (КС) грамматики. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:

  • A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈VN. То есть грамматика допускает появление в левой части правила только нетерминального символа.

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

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

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

  • A→Bγ или A→γ, где γ∈VT*, A∈VN (для леволинейных грамматик).

  • A→γB; или A→γ, где γ∈VT*, A∈VN (для праволинейных грамматик).

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

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

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

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

Формальная грамматика

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

Порождающие грамматики

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

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

Итак, грамматика определяется следующими характеристиками:

  • Σ — набор (алфавит) терминальных символов

  • N — набор (алфавит) нетерминальных символов

  • R — набор правил вида: «левая часть» «правая часть», где:

    • «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал

    • «правая часть» — любая последовательность терминалов и нетерминалов

  • S — стартовый (начальный) символ из набора нетерминалов.

Вывод

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

Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.

Аналитические грамматики

Порождающие грамматики - не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.


Похожие:

Иерархия Хомского iconВопросы к зачету/экзамену по спецкурсу «Языки и автоматы»
...
Иерархия Хомского iconТезисы доклада: Ранний вариант теории Н. Хомского как объяснительная лингвистическая теория
Хомского (в полном соответствии с его собственной оценкой) как «лингвистическую теорию, объясняющую определенный круг языковых явлений»...
Иерархия Хомского iconИерархия 1931 сознание
Как претворить горчайшее в сладчайшее? Ничто не преобразит жизнь в надземное сознание, как Иерархия
Иерархия Хомского iconЦерковная иерархия Иерархия священнослужителей
Черное" духовенство это монашествующие священнослужители (то есть те, которые приняли монашеский постриг); "белое" духовенство женатые...
Иерархия Хомского iconСеанс связи с вц посредник. Инесса силы. Структура исполнителей и иерархия б. Д. Ведущие. Представители структуры и. Б. Д
Структуры как Иерархия Бесконечной Души в Земной Реальности третьего уровня плотности. То есть, мы представляем Иерархию в Земной...
Иерархия Хомского iconИерархия слоев представляет собой совокупность вертикально расположенных решающих подсистем
Иерархия слоев представляет собой совокупность вертикально расположенных решающих подсистем Si, как показано на рис 2 Каждая из таких...
Иерархия Хомского iconЭссе По материалам статьи Ноама Хомского
Данная теория положила начало принципиально новой научной парадигме – генеративизму, пришедшему в американском языкознании на смену...
Иерархия Хомского iconИерархия сред

Иерархия Хомского iconВселенная: масштабы и иерархия

Иерархия Хомского iconИ. Г. Серова онтология социальных фактов и специфика социальной когниции
Дж. Фодора и Н. Хомского утвердилось мнение о том, что работу каждого модуля, в котором предположительно действует сравнительно небольшое...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org