Скворцов А. Теория автоматов. 2 часть



Теория автоматов Часть 2.

Формальные грамматики и языки. Применение.

Основные понятия и определения

Теория формальных грамматик (ФГ) дает:

— способы задания входных данных;

— способы задания и генерации выходных данных;

— способы задания функции, алгоритма преобразования входных данных в выходные;

— способы анализа входных данных

и др.

Основное применение ФГ:

— разработка собственных компиляторов;

— разработка переводчиков;

— преобразование строк, массивов;

— разработка поисковых запросов.

Опр. Алфавит V — конечное непустое множество элементов, называемых символами (буквами).

Опр. Цепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.

Пример. Пусть алфавит V = {a,b,c}. Тогда baaa является словом в алфавите V.

Опр. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается ().

Опр. Длиной цепочки w называется число составляющих ее символов (обозначается |w|), причём каждый символ считается столько раз, сколько раз он встречается в w.

Пример. Очевидно, |baaa| = 4 и || = 0.

Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку , а через V+ — множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .

Пример. Пусть V = {1,0}, тогда V* = {,0,l,00,01,10,11,000,…},

а V+ ={0,1,00,01,10,11,000,…}.

Опр. Если х и у — слова в алфавите V, то слово ху (результат приписывания слова у в конец слова х) называется конкатенацией (катенацией, сцеплением) слов х и у. Иногда конкатенацию слов х и у обозначают х у.

Опр. Если х — слово и п  N, то через хп обозначается слово х х x. По определению х0 = .

Пример. ba3 = bааа и (ba)3 = bababa.

Опр. Говорят, что слово х — префикс (начало) слова у, если у = хи.

Опр. Говорят, что слово х — суффикс (конец) слова у, если у = их.

Опр. Говорят, что слово х — подслово слова у, если у = uxv для некоторых слов и и v.

Опр. Через |w|a обозначается количество вхождений символа а в слово w.

Пример. Если V = {a,b,c}, то |baaa|а = 3, |baaa|b = 1 и |baaa|c = 0.

Опр. Формальный язык – это множество конечных слов (строк, цепочек) над конечным алфавитом V.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения, разности и дополнения языков, заданных над одним и тем же алфавитом (обозначения L1  L2, L1  L2, L1 — L2).

Пример. Множество {a, abb} является языком над алфавитом {a,b}.

Пример. Множество {akbal | k ≤ l} является языком над алфавитом {a,b}.

Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={}≠0.

Опр. Пусть L – язык над алфавитом V*. Тогда язык V* — L называется дополнением языка L относительно алфавита V. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык V* — L является дополнением языка L.

Опр. Грамматика – система правил, предназначенная для задания множества цепочек и символов данного алфавита. G – грамматика; L(G) – язык этой грамматики.

Выделяют 3 группы формальных грамматик:

1. Порождающие (позволяют строить правильную цепочку в заданном алфавите с описанием ее строения и не позволяют строить ни одной неправильной цепочки).

2. Распознающие (позволяют определить к каждой входной цепочке: является ли она правильной; в случае положительного ответа распознающая ФГ выдает строение цепочки).

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

Способы описания языков

Конечный язык можно описать простым перечислением его цепочек.

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

Можно выделить два основных подхода для такого представления: механизм распознавания и механизм порождения (генерации).

Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.

Примеры распознавателей:

Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-зависимые языки.

Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная бесконечная память (магазин, или стек), работающая по дисциплине LIFO. Определяет контекстно-свободные языки.

Конечный автомат (КА). Отличается от МП-автомата отсутствием магазина. Определяет регулярные языки.

Основной способ реализации механизма порождения — использование порождающих грамматик, которые иногда называют грамматиками Хомского. Порождающие ФГ являются наиболее важными и распространенными.

Порождающей ФГ называется четверка вида: G = (VT,VN,P,S),

где VN конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

VT множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VTVN =0;

Р — множество правил вывода грамматики; элемент (α,β) множества Р называется правилом вывода и записывается в виде α→β (читается: «из цепочки α выводится цепочка β»)

S — начальный символ грамматики, S VN.

Для записи правил вывода с одинаковыми левыми частями вида α→β1, α→β2,…,α→βn используется сокращенная форма записи α→β1|β2|…|βn.

Пример. Грамматика G1=({0, 1}, {A, S}, Р1, S), где множество Р1 состоит из правил вида: 1) S→0A1; 2) 0А→00А1; 3)А→.

Опр. Цепочка β (VT VN)* непосредственно выводима из цепочки α(VTVN)+ в грамматике G = (VT,VN,P,S) (обозначается: αβ), если α=ξ1γξ2 и β=ξ1δξ2 , где ξ1,ξ2,δ  V*, γV+ и правило вывода γ→δ содержится во множестве Р.



Опр. Цепочка βV* выводима из цепочки αV+ в грамматике G =(VT,VN,P,S) (обозначается: α*β), если существует последовательность цепочек γ0,γ1,…,γn (n≥0) такая, что α=γ0γ1…γn=β.

Пример. В грамматике G1 S=>*000111, т.к. существует вывод S => 0А1=> 00А11 => 000A111 => 000111.

Опр. Языком, порожденным грамматикой G = (VT, VN,P,S), называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамматики S с помощью правил множества Р, т.е. множество L(G)= {αV* |S*α}.

Пример. Для грамматики G1 L(G1)={0n1n | п>0}.

Опр. Цепочка αV*, для которой существует вывод S*α, называется сентенциальной формой в грамматике G = (VT, VN,P, S).

Опр. Грамматики G1 и G2 называются эквивалентными, если L(G1) =L(G2).

Пример. Для грамматики G1 эквивалентной будет грамматика G2 =({0, 1}, {S}, Р2, S), где множество правил вывода Р2 содержит правила вида S→0S1|01.

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

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

Тип 0. (формальные грамматики с фразовой структурой, неограниченные). Грамматика G = (VT, VN,P, S) называется грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений, кроме тех, которые указаны в определении грамматики. Любое правило α→β может быть построено с использованием произвольных цепочек α, β(VTVN). Этот тип грамматик самый общий, включающий все грамматики. Однако некоторые грамматики могут принадлежать только к этому типу. Практического применения в силу своей сложности такие грамматики не имеют. Например:

P = TR→HT или abC→xDa.

Тип 1. (контекстно-зависимые, контекстные грамматики, грамматика непосредственно составляющих, НС-грамматика). К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики.

Грамматика G = (VT,VN,P,S) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN.

Грамматика G = (VT,VN,P,S) называется неукорачивающий грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN и |A|<=|γ|.

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

Тип 2. (Контекстно-свободной грамматикой, КС-грамматикой, бесконтекстной грамматикой). Грамматика G = (VT,VN,P,S) называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈VN. То есть грамматика допускает появление в левой части правила только нетерминального символа. КС-грамматики широко применяются для описания синтаксиса компьютерных языков (программирования).

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

грамматики могут быть разделены на два эквивалентных класса:

 Грамматика G = (VT, VN, Р, S) называется праволинейной, если ее правила вывода имеют вид A→γB или A→γ, где γ∈VT*, A, B∈VN;

 Грамматика G = (VT, VN, Р, S) называется леволинейной, если ее правила вывода имеют вид A→Bγ или A→γ, где γ∈VT*, A, B∈VN.

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

Контекстно-свободные грамматики и языки

КС грамматики широко используются в практике программирования как способ задания формализованных языков. КС грамматики способны выразить большую часть синтаксиса языков программирования. Применяются также при описании языков HTML, XML, языка описания документов DTD и других.

Определение. Язык называется контекстно-свободным, если существует контекстно-свободная грамматика, его порождающая.

Пример. Возьмем язык палиндромов. Это цепочки символов, читающиеся одинаково справа и слева.

otto madam madamimadam

Для упрощения рассмотрим палиндромы в алфавите {0, 1}.

00100 10101

Выразим определение языка палиндромов в виде КС-грамматики:

Формальные языки и теория автоматов

Первые три правила говорят, что язык палиндромов включает цепочки из пустых символов, 0 и 1.

Четвертое и пятое правила – если взять произвольную цепочку w из языка Р, то 0w0 и 1w1 также будут в языке Р.

Формальные языки и теория автоматов

Эти 4 компонента образуют КС-грамматику. Будем представлять КС-грамматику в виде:

G = (V, T, P, S),

где V – множество переменных, T – терминалов, P – правил вывода, S – стартовый символ.

Пример 1.

Gpal = ({P}, {0, 1}, A, P)

где А – вышеприведенные правила вывода.

Грамматика Gpal порождает цепочки языка палиндромов: 10101, 01010, 0110, …

Выведем первую цепочку с помощью грамматики палиндромов:

P → 1P1 → 10P01 → 10101

Пример 2.

Допустим язык выражений типичного языка программирования состоит из идентификаторов, которые начинаются с буквы a или b, за которой следует цепочка {a,b,0,1} и арифметических операторов + и * .

( a + b ) * ( a + b + a0 + a1 )

Введем для грамматики 2 переменные:

Е – выражения языка, стартовый символ

I – идентификаторы языка

Формальные языки и теория автоматов

Gвыр= ({Е, I}, {a, b, 0, 1, +, *}, A, E)

где A = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 }

Упрощенная запись грамматики:

Gвыр = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 }

Теперь рассмотрим, как выводится из построенной грамматики вышеуказанная цепочка

( a + b ) * ( a + b + a0 + a1 )

E → E*E → (E)*(E) → (E+E)*(E+E) → (I+I)*(E+E+E+E) → (a+b)*(I+I+I+I) →

→ (a+b)*(a+b+I0+I1) → (a+b)*(a+b+a0+a1)

Вывод в КС-грамматике удобно представлять с помощью дерева вывода.

Закрепление материала:

1. Составить последовательность вывода цепочки 101101 из грамматики палиндромов.



2. Составить последовательность вывода цепочки (a+b0)*a0+b из грамматики выражений.

Дерево вывода и неоднозначность грамматик

Определение. Деревом вывода цепочки w ϵ Т в грамматике G = (V, T, P, S) называется упорядоченное дерево, узлы которого помечены символами из множеств V, T так, что корень дерева помечен аксиомой (стартовым символом), внутренние узлы – нетерминалами, а листья – терминалами.

Пример.

Построим дерево вывода цепочки ( a + b ) * ( a + b + a0 + a1 ) из грамматики выражений.

Корень дерева Е, внутренние узлы E и I, листья – заданная цепочка.

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

E

E

*

(

)

Е

E

(

)

Е

Е

Е

+

Е

Е

+

Е

Е

+

Е

Е

+

I

I

I

I

I

I

a

b

a

b

I

I

0

1

a

a

E

E

*

(

)

Е

E

(

)

Е

Е

Е

+

Е

Е

+

Е

Е

+

Е

Е

+

I

I

I

I

I

I



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст




sitemap
sitemap