yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->                 7.2   Классификация грамматик

Дискретная математика

                 7.2   Классификация грамматик

 

   Общепринятой классификацией грамматик и порождаемых ими  языков является иерархия Хомского, содержащая четыре типа грамматик:

 

    г==========================================================¬

    ¦ 0-тип   - грамматики с фразовой структурой.              ¦

    ¦   x -> y;     x и y - любые цепочки терминалов и нетерм. ¦

    ¦ ---------------------------------------------------------¦

    ¦ ¦ 1-тип  - контекстно-зависимые грамматики               ¦

    ¦ ¦  x -> y;    ¦x¦ <=¦y¦ (правая цепочка не короче левой);¦

    ¦ ¦ -------------------------------------------------------¦

    ¦ ¦ ¦ 2-тип  - контекстно-свободные грамматики             ¦

    ¦ ¦ ¦  A -> y;     A - нетерминал, y - любая цепочка;      ¦

    ¦ ¦ ¦ -----------------------------------------------------¦

    ¦ ¦ ¦ ¦ 3-тип  - автоматные грамматики                     ¦

    ¦ ¦ ¦ ¦  A -> aB  A => b; a,b-терминалы; A,B - нетерминалы ¦

    L==========================================================-

   Каждый тип грамматик включает грамматики более  высоких  типов,

как частные случаи.

 

 

 

 

38