Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7

Вид материала

Конспект

Содержание 5. Классификация грамматик 6. А-языки. Конечные лингвистические автоматы 6.1. Диаграмма грамматики

Подобный материал:

• Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
• Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
• Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
• Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
• Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
• Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
• Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
• Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
• Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
• Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.

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

Выделяются определенные классы грамматик, основными среди которых являются контекстно-свободные (КС), контекстно-зависимые (КЗ), автоматные…

Основными типами грамматик являются:

Грамматики класса «0» – не накладываются ограничения на вид правила.

Контекстно-зависимые (КЗ-грамматики), все правила которых имеют вид   , где (V_TV_N)*V_N(V_TV_N)*,  (V_TV_N )*     .

Например, этому классу принадлежит грамматика G₄ с правилами

S  abA ab , bA  Ab , aA  aabA , aA  aab .

Контекстно-свободные (КС-грамматики) – грамматики, все правила которых имеют вид А , где АV_N ,  (V_TV_N )*.

Например, это грамматика G₅ с правилами S  a S b ab , L(G₅) = L(G₄)= {aⁿbⁿ, n>0}.

Автоматные грамматики (А-грамматики) – это грамматики, все правила которых имеют вид Аа, Аa B, А, aV_T, A,B V_N.

Иногда выделяется еще один класс грамматик: контекстные грамматики, или грамматики класса 1, все правила которых имеют вид , где , (V_TV_N), A V_N, (V_TV_N )*.

Здесь пара цепочек  и  составляет неизменяемый контекст правила. Между контекстными грамматиками и КЗ-грамматиками существует взаимно-однозначное соответствие, не всегда очевидное. По выразительной мощности эти классы грамматик совпадают, однако, поскольку для одного и того же языка контекстная грамматика содержит большее число правил, мы будем изучать именно КЗ-грамматики.

Пример.

Грамматика G₆, КЗ-грамматика с правилами

S aAc , A aABc , A b , bBbb , cB Bc .

L(G6)= {anbncn, n.

Эквивалентная G₆ контекстная грамматика G₇ с правилами

S аBC , B аBDC , B b , bDbb , CD ED , ED EC , EC DC , Cc .

L(G7)= {anbncn, n

В ней правило переноса символа B заменяется на три правила.

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

А-язык – язык, для которого может быть построена порождающая его А-грамматика.

КЗ-язык – язык, который может быть построен только КЗ-грамматикой.

Непосредственная классификация грамматик выглядит следующим образом.

Класс А-грамматик включается в класс КС-грамматик. Все грамматики принадлежат классу 0.

Однако класс КС-грамматик не включается в класс КЗ-грамматик, так как правила вида А могут принадлежать КС-грамматикам, но не КЗ-грамматикам, так как А.

Поэтому общий вид классификации грамматик следующий:

6. А-языки. Конечные лингвистические автоматы

6.1. Диаграмма грамматики

Пусть дана А-грамматика G=< V_N, V_T, S, R> . Диаграмма А-грамматики – граф с помеченными вершинами и дугами. Множество вершин графа соответствует множеству нетерминалов А-грамматики, приведенной к каноническому виду, а множество дуг – множеству правил грамматики.

Приведение грамматики к каноническому виду:

1. Вводим дополнительный нетерминальный символ К, тогда V_N’= V_N  К.
   
2. Заменяем правила вида Аа на правила АаК.
   
3. Вводим дополнительное правило К.
   

Таким образом, все правила грамматики теперь приобрели "стандартный" вид AaB или A.

Построение диаграммы опишем следующими правилами.

1. Каждому нетерминальному символу поставим в соответствие вершину и пометим ее этим символом.

2. Каждому правилу AaB сопоставим дугу из вершины A в вершину В и пометим ее терминальным символом а.

3. Отметим в графе как начальную вершину – вершину, соответствующую начальному символу, и как заключительные – все такие вершины В, что B (на диаграмме используется символ #).

Пример. Пусть грамматика G₈ описывается правилами:

S aBbC , B bbB , C aS .

Грамматика в канонической форме будет иметь вид:

S aBbC , B bKbB , C aS , K  .

Диаграмма грамматики приводится на рис.1.

Рис.1	Рис.2

Очевидно, что существует взаимно однозначное соответствие между грамматикой в каноническом виде и диаграммой.

Например, рассмотрим диаграмму грамматики, представленную на рис.2. Очевидно, что диаграмме соответствует грамматика G₉ с правилами

S aSaB , B bKbB , K  .