Типы грамматик и их свойства

Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.

Определение. Пусть дана грамматика G = (N, T, P, S). Тогда

(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.

(2) если

каждое правило грамматики, кроме
, имеет вид
, где
, и
в том случае, когда
, символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей или контекстно-зависимой (КЗ- грамматикой) или контекстно - чувствительной (КЧ- грамматикой).

(3) если каждое правило грамматики имеет вид

, где

, то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).

(4) если каждое правило грамматики имеет вид либо

, либо

, где

то ее называют грамматикой типа 3, или праволинейной.

Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.

Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.

Содержание раздела