Порождающая грамматика g это четверка



Дата23.02.2018
өлшемі445 b.





Порождающая грамматика G - это четверка

  • Порождающая грамматика G - это четверка

  • G = (T, N, P, S) , где

  • T – непустое множество терминальных символов

  • ( алфавит терминалов ),

  • N – непустое множество нетерминальных символов

  • (алфавит нетерминалов), не пересекающийся с T,

  • P - конечное подмножество множества (T  N)+  (T  N)*.

  • Элемент (, ) множества P называется правилом вывода и записывается в виде

  •  → ,

  • причем содержит хотя бы один нетерминальный символ.

  • S - начальный символ (цель) грамматики, S  N.

  • Декартовым произведением A  B множеств A и B называется множество { (a,b) | a  A, b  B}.



1) Большие латинские буквы будут обозначать нетерминальные символы.

  • 1) Большие латинские буквы будут обозначать нетерминальные символы.

  • 2) S - будет обозначать начальный символ (цель) грамматики.

  • 3) Маленькие греческие буквы будут обозначать цепочки символов.

  • 4) Все остальные символы (маленькие латинские буквы, знаки операций и пр.) будем считать терминальными символами.

  • 5) для записи правил вывода с одинаковыми левыми частями

  •   1   2 ...   n

  • будем пользоваться сокращенной записью

  •   1 | 2 |...| n.

  • Каждое i , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки .

  • Пример грамматики:

  • G1 = ( {0,1}, {A,S}, P, S), где P состоит из правил:

  • S  0A1

  • 0A  00A1

  • A  







ТИП 0:

  • ТИП 0:

  • Грамматика G = (T, N, P, S) - грамматика типа 0, если на ее правила вывода не накладывается никаких ограничений.

  • ТИП 1:

  • Грамматика G = (T, N, P, S) - неукорачивающая грамматикой, если каждое правило из P имеет вид

  •  → , где   (T  N)+,   (T  N)+ и |  | <= |  |.

  • Исключение - в неукорачивающей грамматике допускается наличие правила S → , при условии, что S (начальный символ) не встречается в правых частях правил.

  • Грамматика G = (T, N, P, S) - контекстно-зависимая ( КЗ ), если каждое правило из P имеет вид

  •  → , где  = 1 A 2;  = 1  2; A  N;   (T  N)+; 1, 2  (T  N)*.

  • В КЗ-грамматике допускается Исключение.

  • Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.



ТИП 2:

  • ТИП 2:

  • Грамматика G = (T, N, P, S) - контекстно-свободная ( КС ), если каждое правило из Р имеет вид A → , где A  N,   (T  N)*.

  • Грамматика G = (T, N, P, S) - неукорачивающая контекстно-свободная (НКС), если каждое правило из Р имеет вид A , где A  N,   (T  N)+.

  • В неукорачивающей КС-грамматике допускается Исключение.

  • Грамматику типа 2 можно определить как контекстно-свободную либо как неукорачивающую контекстно-свободную.

  • ТИП 3:

  • Грамматика G = (T, N, P, S) - праволинейная, если каждое правило из Р имеет вид имеет вид: A → wB либо A → w, где ABN, w*.

  • Грамматика G = (T, N, P, S) - леволинейная, если каждое правило из Р имеет вид: A → Bw либо A → w, где AB  N, w  T *.

  • Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.

  • Автоматная грамматика - праволинейная (леволинейная) грамматика, такая, что каждое правило с непустой правой частью имеет вид: A → a либо A → aB

  • (для леволинейной, A → a либо A → Ba), где AB  N, a  T.



  • неук. Р  неук. КС  КЗ  Тип 0

  • Любая регулярная грамматика является КС-грамматикой.

  • Любая неукорачивающая КС-грамматика является КЗ-грамматикой.

  • (3) Любая неукорачивающая грамматика является грамматикой типа 0.

  • Язык L(G) является языком типа k по Хомскому, если его можно описать грамматикой типа k, где k - максимально возможный номер типа грамматики по Хомскому.



  • Р  КС  КЗ  Тип 0

  • Каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными

  • ( например, L = { an bn | n > 0 }).

  • Каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками

  • ( например, L = { an bn cn | n > 0 }).

  • Каждый КЗ-язык является языком типа 0, но существуют языки типа 0, которые не являются КЗ-языками

  • (например: язык, состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите).

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

  • Проблема, можно ли язык, описанный грамматикой типа k, описать грамматикой типа k + 1 (k = 0, 1, 2), является алгоритмически неразрешимой.





Каталог: n10


Достарыңызбен бөлісу:


©stom.tilimen.org 2019
әкімшілігінің қараңыз

    Басты бет