Лекции.Орг


Поиск:




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

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.
Определение 1.9. Формальной грамматикой называется четверка вида:

, (1.1)

где VN - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);
VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры и т.п.), VT Ç VN = Æ;
Р - множество правил вывода грамматики, являющееся конечным подмножеством множества (VT È VN) + ´(VT È VN) *; элемент (a, b) множества Р называется правилом вывода и записывается в виде a ® b (читается: «из цепочки a выводится цепочка b»);
S - начальный символ грамматики, S принадлежащий N.

Классификация грамматик в иерархии американского математика Хомского осуществляется по структуре правил вывода. В расширенной иерархии Хомского выделяется четыре типа грамматик.

Тип 0. Грамматика называется грамматикой типа 0 (грамматикой без ограничений или грамматикой с фразовой структурой), если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

Тип 1. Грамматика называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид a ® b, где a Î (VT È VN)+, b Î (VT È VN)* и | a | £ | b |. Расширение допускает не более одного e -правила, т.е. правила вида А ® e, А Î VN.
Тип 2. Грамматика называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: , где и
Тип 3. Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной вправо, если ее правила вывода имеют вид, где .
Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной влево, если ее правила вывода имеют вид , где .

Расширение допускает единственное e-правило вида S®e, но в этом случае начальный символ грамматики S не должен встречаться в правых частях правил.

Определение 1.15. Язык L (G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.
Пример 1.7. Языквида L= {0 n 1 n | n >0} порождается КЗ-грамматикой (тип 1) G 1 (пример 1.4) и КС-грамматикой (тип 2) G 2= ({0, 1}, { S }, P 2, S), где
множество правил вывода P 2 содержит правила вида S ® 0 S 1|01.
Так как не существует регулярной грамматики (тип 3), порождающей данный язык, то язык L является языком типа 2 или КС-языком.
Соотношение типов грамматик и языков представлено на рисунке 1.1.

Р – регулярная грамматика;КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;
Тип 0 – грамматика типа 0.

Рисунок 1.1 – Соотношение типов формальных языков и грамматик

Пример 1.8. Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L (G)= определяется грамматикой с правилами вывода:

  • 1) S ® aaCFD;
  • 2) AD ® D;
  • 3) F ® AFB | AB;
  • 4) Cb ® bC;
  • 5) AB ® bBA;
  • 6) CB ® C;
  • 7) Ab ® bA;
  • 8) bCD ® e.

б) Контекстно-зависимый язык L (G)={ anbncn | n ³1} определяется грамматикой с правилами вывода:

  • 1) S ® aSBC | aBC;
  • 2) CB ® BC;
  • 3) aB ® ab;
  • 4) bB ® bb;
  • 5) bC ® bc;
  • 6) cC ® cc.

в) Контекстно-свободный язык L (G)={() n (cb) n | n >0} определяется грамматикой с правилами вывода:

  • 1) S ® aQb | accb;
  • 2) Q ® cSc.

г) Регулярный язык L (G)={ w ^ | w Î{ a, b }+, где нет двух рядом стоящих а } определяется грамматикой с правилами вывода:

  • 1) S ® A ^ | B ^;
  • 2) A ® a | Ba;
  • 3) B ® b | Bb | Ab.

Определение 1.16. Грамматики G 1 и G 2 называются эквивалентными, если они определяют один и тот же язык, т.е. .
Определение 1.17. Грамматики G 1 и G 2 называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов, т.е. .
Пример 1.9. Для грамматики G 1 эквивалентной будет грамматика G 2 = ({0, 1}, { S }, P 3, S), где P 2: S ® 0 S 1|01, т.к. L (G 1)= L (G 2)={0 n 1 n | n >0} (пример 1.7).

Почти эквивалентной для грамматики G 1 будет грамматика G 3 = ({0, 1}, { S }, P 3, S), где множество правил вывода P 3 содержит правила вида S ® 0 S 1| e, т.к. L (G 3)={0 n 1 n | n ³0}.

 



<== предыдущая лекция | следующая лекция ==>
Согласно управленческой решетки Р.Блейка и ДЖ. Моутона оптимальным стилем руководства является стиль | Оцените заявления сторон договора. Дайте юридическую квалификацию отношений сторон
Поделиться с друзьями:


Дата добавления: 2016-10-07; Мы поможем в написании ваших работ!; просмотров: 473 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Самообман может довести до саморазрушения. © Неизвестно
==> читать все изречения...

1047 - | 901 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.