Page 19 - 4625

Залежно від структури правил граматики поділяються на
чотири типи (класифікація граматик за Хомським):
- тип 0: граматики загального виду, коли правила не
мають обмежень, тобто:
  ,   (N)* N (N)*,   (N);
*
*
- тип 1: граматики, що не укорочуються, коли обме-
ження на правила мінімальні, а саме:
  ,   (N)* N (N)*,   (N) *, || <= ||;
* *
- тип 2: контекстно-вільні граматики, коли правила в
схемі P мають вигляд:
A  , A  N,   (N)*;
i
i
- тип 3: скінченноавтоматні граматики, коли правила в
схемі P мають вигляд:
∗
A wA , A , A  N, w ∈ Σ ;
j
i
i
j
∗
A w, w ∈ Σ ;
i
∗
A wA , A , A  N, w ∈ Σ .
j
j
i
i
У класі скінченноавтоматних граматик виділимо так зва-
ні праволінійні граматики – це граматики, які в схемі Р мають
правила вигляду:
∗
A wA , A , A  N, w ∈ Σ .
i
j
i
j
Нескладно довести, що клас праволінійних граматик
співпадає з класом граматик типу 3.
Означення:
1. Ланцюжок w безпосередньо виводиться з ланцюжка w
1
(позначається w  w ), якщо w = xy, w = xy та в схемі
1
1
Р граматики G є правило виведення Оскільки поняття
«безпосередньо виводиться» розглядається на парах ланцюж-
ків, то символ  в подальшому буде трактуватися як бінарне
відношення.
2. Ланцюжок w виводиться з ланцюжка w (позначається
1
1
w * w ), якщо існує скінчена послідовність виду w  w ,
1
18