Перечислите основные типы грамматик по классификации Хомского. Какому типу соответствуют алгоритмические языки?

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

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

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

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

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

Что такое регулярные (автоматные) грамматики? Какие типы распознающих устройств используются для распознавания регулярных грамматик?

Распознающие, порождающие формальные грамматики

Формальные грамматики задают правильные цепочки, если для любой предъявленной цепочки грамматика позволяет установить, является или нет эта цепочка

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

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

Структурные методы распознавания базируются на порождающей грамматике – системе, состоящей из четырех частей: основной, или терминальный словарь; вспомогательный словарь; начальный символ; набор правил подстановки исходных элементов, из которых строят цепочки, порождаемые грамматикой. Элементы основного словаря называют основными (терминальными) символами.

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

Начальный символ. Это выделенный нетерминальный символ, обозначающий совокупность (класс) всех тех языковых объектов, для описания которых предназначается данная грамматика. Так в грамматике, порождающей предложения, начальным будет символ, означающий предложение; в грамматике, порождающей допустимые слоги, начальный символ означает слог, и т. п.

Правила подстановки. Это выражения вида «X → Y», „Х вместо Y“, где Х и Y – цепочки, содержащие любые терминальные или нетерминальные символы.

Понятие распознающего устройства (распознавателя, автомата)

Для каждого языка важно не только возможность создания текстов на этом языке, но и возможность определения принадлежности имеющегося текста к данному языку.

Распознающее устройство (распознаватель, автомат) – это специальный алгоритм, который позволяет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет.

Распознаватель можно отобразить в виде условной схемы:

Распознаватель состоит из следующих основных компонентов:

· ленты, содержащей исходную цепочку входных символов, и считывающей головки, обозревающей очередной символ в этой цепочке;

· устройства управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);

· внешней (рабочей) памяти, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти УУ может иметь неограниченный объем.

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

Конфигурация распознавателя определяется следующими параметрами:

· содержимое входной цепочки символов и положение считывающей головки в ней;

· состояние УУ;

· содержимое внешней памяти.

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

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

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

Классификация распознавателей по виду их компонентов

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

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

Двусторонние распознаватели допускают, что считывающая головка может перемещаться относительно ленты входных символов в обоих направлениях: как вперед, от начала ленты к концу, так и назад, возвращаясь к уже прочитанным символам.

По видам устройства управления распознаватели бывают детерминированные и недетерминированные.

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

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

По видам внешней памяти распознаватели бывают следующих типов:

· распознаватели без внешней памяти;

· распознаватели с ограниченной внешней памятью;

· распознаватели с неограниченной внешней памятью.

У распознавателей без внешней памяти эта память полностью отсутствует. В процессе их работы используется только конечная память устройства управления, доступ к внешней памяти не выполняется.

Для распознавателей с ограниченной внешней памятью размер внешней памяти ограничен в зависимости от длины исходной цепочки символов. Эти ограничения могут налагаться некоторой зависимостью объема памяти от длины цепочки. Кроме того, для таких распознавателей может быть указан способ организации внешней памяти — стек, очередь, список и т. п.

Распознаватели с неограниченной внешней памятью предполагают, что для их работы может потребоваться внешняя память неограниченного объема (как правило, вне зависимости от длины входной цепочки). У таких распознавателей предполагается память с произвольным методом доступа.

Вместе эти три составляющих позволяют организовать общую классификацию распознавателей. Например, в этой классификации возможен такой тип: «двусторонний недетерминированный распознаватель с линейно ограниченной стековой памятью».

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

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

Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имеющий неограниченную внешнюю память. Поэтому для языков данного типа нельзя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Практическая реализация таких распознавателей чрезвычайно сложна.

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

Автоматы данного типа имеют экспоненциальную сложность: время, необходимое на разбор входной цепочки, экспоненциально зависит от длины входной цепочки символов. Такой алгоритм распознавателя может быть реализован в программном обеспечении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуются. Как правило, такие распознаватели применяются для автоматизированного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны. После обработки естественноязыковых текстов часто требуется ручное постредактирование.

Для контекстно-свободных языков (тип 2) распознавателями являются односторонние детерминированные / недетерминированные автоматы с магазинной (стековой) внешней памятью — МП-автоматы. В общем случае, автоматы данного типа имеют экспоненциальную сложность, однако алгоритм можно усовершенствовать так, чтобы его сложность стала полиномиальной (кубической). Среди всех КС-языков можно выделить класс детерминированных КС-языков, распознавателями для которых являются детерминированные автоматы с магазинной (стековой) внешней памятью — ДМП-автоматы. Эти языки обладают свойством однозначности (доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику). Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложностью. Более того, среди детерминированных КС-языков существуют такие классы языков, для которых возможно построить линейный распознаватель (где время принятия решения о принадлежности цепочки языку имеет линейную зависимость от длины цепочки).

Для регулярных языков (тип 3) распознавателями являются детерминированные автоматы без внешней памяти — конечные автоматы (КА). Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Кроме того, конечные автоматы имеют важную особенность: любой недетерминированный КА всегда может быть преобразован в детерминированный. Простота и высокая скорость работы распознавателей определяют широкую область применения регулярных языков.

В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Задание набором правил

Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.

правая регулярная грамматика - все правила могут быть в одной из следующих форм:

A → a

A → aB

A → ε

левая регулярная грамматика - все правила могут быть в одной из следующих форм:

A → a

A → Ba

A → ε

где

заглавные буквы (A, B) обозначают нетерминалы из множества N

строчные буквы (a, b) обозначают терминалы из множества Σ

ε - пустая строка, т.е. строка длины 0

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

[править]

Пример

Правая регулярная грамматика G, заданная N = {S, A}, Σ = {a, b, c}, P состоит из следующих правил:

S → aS

S → bA

A → ε

A → cA

и S является начальным символом. Эта грамматика описывает тот же язык, что и регулярное выражение a*bc*.

[править]

Ограниченность

Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных (для контекстно-свободных грамматик допустимо наличие тех и других одновременно). Следовательно, такие грамматики могут выразить все контекстно-свободные языки. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные, но не оба вида одновременно. Поэтому они могут описать лишь подмножество языков, называемых регулярными языками.

Например, контекстно-свободный язык строк вида aibi, i≥0 задается грамматикой G, где N = {S, A}, Σ = {a, b}, P состоит из правил

S → aA

A → Sb

S → ε

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