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

1. Порождающие грамматики

ПОРОЖДАЮЩИЕ
ГРАММАТИКИ

2. Порождающая грамматика (Кс-грамматика) -

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

3. Что такое язык?

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

4. Примеры грамматики

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

5. Примеры грамматики

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

6. Примеры грамматики

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

7. Задания

ЗАДАНИЯ
1.
Написать грамматику, которая
порождает бесконечную цепочку
aaaaaaaaa……………….a
2.
Написать грамматику,
порождающую цепочку, состоящую
из четного количества символов.