Типы грамматик

Сложность
Трудный 80%

Грамматика

Вводя более или менее ограничительные критерии вида грамматических правил, мы получаем иерархические классы грамматик (типы грамматик), упорядоченные по включению. Классификация грамматик, определенная в 1957 году Ноамом Хомским, выделяет четыре класса.

классификация Хомского

Тип 0: никаких ограничений по правилам.

Тип 1: контекстно-зависимые или контекстные грамматики. Правила R имеют вид:

  • uAv → uwv, где A ∈ N, u, v ∈ (N ∪ T)и w ∈ (N ∪ T)+
  • Другими словами, нетерминальный символ A заменяется на w, если у нас есть контексты u слева и v справа.

Тип 2: контекстно-свободные грамматики. Правила R имеют вид:

  • A → w, где A ∈ N и w ∈ (N ∪ T)*
  • Другими словами, левый член каждого правила состоит из одного нетерминального символа.

Тип 3: обычные грамматики

  •  Направо. Правила R имеют вид
    A → aB или A → a, где A, B ∈ N и a ∈ T
  • Слева. Правила R имеют вид
    A → Ba или A → a, где A, B ∈ N и a ∈ T
  • То есть левый член каждого правила состоит из одного нетерминального символа, а правый член состоит из терминального символа и, возможно, нетерминального символа. Для праворегулярных грамматик нетерминальный символ всегда должен быть справа от терминального символа, а для леворегулярных грамматик — слева.

Пример 1

Мы рассматриваем язык L слов на {0, 1}, которые представляют беззнаковые четные целые числа по основанию 2 (все слова этого языка оканчиваются на 0 и не начинаются с 0, за исключением нулевого целого числа). Формально определите L и постройте регулярную грамматику, описывающую L.

Язык имеет следующий вид: L = {0, 1u0/ u ∈ {0, 1}*}

Определим правую регулярную грамматику G = (T, N, S, R), где
Т = {0, 1}
N = {S, U}
р знак равно { S → 0 | 1U
У → 1У | 0У | 0 }
а также левая регулярная грамматика G = (T, N, S, R), где
Т = {0, 1}
N = {S, U}
р знак равно { S → 0 | U0
У → У1 | U0 | 1 }

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

Пример 2

Вот грамматические произведения: P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → ε. Нетерминалы грамматики — {P,Q,R}, начальный символ — P.

Обозначая через Xп, ИКСд, ИКСр языков, принятых из состояний P, Q и R соответственно, система уравнений для этих языков такова:

грамматика

Делиться
ru_RURU