Классификация грамматик по Хомскому.

Глава 2. Способы задания языков

Теория формальных языков (формальных грамматик) занимается описанием, распознаванием и переработкой языков. Описание любого языка должно быть конечным, хотя сам язык мо­жет содержать бесконечное множество цепочек. Полезно иметь возможность описания отдельных типов языков, имеющих те или иные свойства, т. е. иметь различные типы конечных описаний. Синтаксис языка можно задать с использованием синтаксических диаграмм или другим альтернативным способом, воспользовавшись нотацией Бэкуса-Наура (НБН). При ис­пользовании нотации Бэкуса-Наура нетерминальные символы (подлежащие дальнейшему определению) языка заклю­чаются в угловые скобки вида <... >.

Последовательность символов:: = означает «определя­ется как», а символ | означает "или". Пример описания в нотации Бэкуса-Наура арифметических выражений, содержащих переменные a, b, приведен ниже.

< выражение >:: = < терм > | < терм > + < выражение > | < терм > - < выражение >

< терм >:: = < множитель > | < множитель > * < терм > | < терм > / < множитель >

< множитель >:: = a|b| (< выражение >)

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

Грамматики.

Основные понятия и обозначения.

Основными объектами грамматики являются базовые элементы языка или терминальные символы, а также цепочки, построенные из этих элементов.

При определении грамматики будем придерживаться следующих соглашений:

· прописными буквами обозначаются нетерминальные символы языка;

· строчными буквами латинского алфавита обозначаются терминальные символы языка;

· цепочки обозначаются либо прописными буквами латинского алфавита, либо греческими буквами.

· символ «→» используется для обозначения отношения "определяется как".

Введем в рассмотрение пустую цепочку ε, не содержащую ни одного символа.

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

B = abab, |B| = |abab | = 4,

| ε | = 0.

Конкатенацией двух цепочек X и Y называется такая цепочка Z, которая получается непосредственным слиянием цепочки X, стоящей слева, и цепочки Y, стоящей справа. Например, если X = ffg, Y = ghh, то конкатенация X и Y – это цепочка Z = ffgghh.

Будем обозначать через А^* множество всех возможных цепочек конечного множества А базовых элементов (символов), включая пустую цепочку ε; Множество А называют также алфавитом. Любое множество цепочек L Í A^* называется формальным языком, определенным на алфавите А.

Классификация грамматик по Хомскому.

Грамматика – это математическая система, определяющая язык. Будем рассматривать класс грамматик, называемых грамматиками Хомского или грамматиками составляющих. В грамматике, определяющей язык L, используется два типа конечных непересекающихся множества символов – множество нетерминальных символов, которое будет обозначаться буквой N, и множество терминальных символов, обозначаемое S. Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для задания слов языка L.

Основу грамматики составляет конечное непустое множество P правил образования слов языка. Правило – это пара

(N È S)^*N(N È S)^* → (N È S)^*.

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

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

Формально грамматика задается четверкой

G = (N, S, P, S),

где N – конечное множество нетерминальных символов;

S – конечное множество терминальных символов, непересекающееся с N;

P – конечное множество правил вида a b, a и b – цепочки, причем a содержит хотя бы один нетерминальный символ, а на цепочку b не наложено никаких ограничений;

S – начальный или исходный символ.

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

На множестве (N S)^* вводятся отношения и ^*. Если aAg b – продукция из P, l и w – цепочки из множества (N S) ^*, то laAgw lbw. То есть продукция aAg b применяется к цепочке laAgw для получения цепочки lbw или, другими словами, цепочка lbw непосредственно получается (порождается, выводится) из цепочки laAgw после применения продукции aAg b. Две цепочки связаны отношением , если вторая цепочка получается из первой применением продукции из P. Пусть имеется

l₁ l₂, l₂ l₃, …, l_m-1 l_m.

Здесь l₁, l₂, …, l_m цепочки из (N ) *. Последовательность приведенных выше отношений может быть записана так: l₁ ^* l_m .

Язык L, порождаемый грамматикой G, – это множество цепочек, которые состоят только из терминальных символов и которые можно вывести из символа S. Формально это можно записать следующим образом:

L = {l | l Î S*, S ^* l}.

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

A xB, A → Bx или A → x, где A, B Î N, x Î S^*.

Грамматика называется контекстно-свободной (бесконтекстной), если каждое правило имеет вид

A → a, где A Î N, a Î (N S)^*.

Грамматика называется контекстно-зависимой (не укорачивающей), если каждое правило имеет вид

a → b, где | a | £ | b |.

Грамматика, не удовлетворяющая ни одному из указанных ограничений, называется грамматикой общего вида или грамматикой без ограничений.

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

Распознаватели.

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

Работа распознавателя складывается изпоследовательности шагов или тактов. За один такт выполняются следующие действия:

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

Поведение распознавателя описывают в терминах конфигураций. В конфигурацию объединена следующая одномоментная информация о распознавателе:

• состояние управляющего устройства;
• содержимое входной ленты и положение входной головки;
• содержимое памяти.

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

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

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

Каждому классу грамматик из иерархии Хомского соответствует класс распознавателей, задающий тот же класс языков. Такими распознавателями являются конечные автоматы, автоматы с магазинной памятью, линейно-ограниченные автоматы и машины Тьюринга.
Глава 3. Регулярные языки