Порождающие грамматики. (Лекция 2)

ПОРОЖДАЮЩАЯ ГРАММАТИКА (КС-ГРАММАТИКА) -
это четверка
V, W – непустые конечные множества
V – терминальный алфавит
W – нетерминальный алфавит
S – аксиома
R – конечное множество правил

ЧТО ТАКОЕ ЯЗЫК?
КС-язык – язык, который может быть задан КС-грамматикой.
То есть, язык – множество всех цепочек, которые можно породить с помощью правил данной грамматики.

ПРИМЕРЫ ГРАММАТИКИ
S ->AB;
A->a;
B->b;
S ->A;
A->Aa;
A->a;
S ->ABC;
A->ab;
B->bB;
C->abc;

ПРИМЕРЫ ГРАММАТИКИ
S
N
V
снег
идет

ПРИМЕРЫ ГРАММАТИКИ
Мой друг читает очень интересную книгу