8.1.Двоично дърво.Представяне.Основни операции
   8.2.Граф.Представяне.Основни операции
   8.3.Пролог и КС-граматики
   8.4.Пресмятане на стойност на аритметичен израз
   8.5.Интерпретатор на подмножество на езика Пролог

    
  8.3. Пролог и КС-граматики

     КС-граматика се дефинира като четворка G = (V, T, P, S), където V е крайно множество от
  нетерминални символи, Т е крайно множество от терминални символи, сечението на Т и V е 
  празното множество, Р е крайно множество от правила (продукции) от вида А -> l, където V э А,
  а l е редица от елементи от множеството V обединено c T и S е особен нетерминален символ, 
  наречен начален символ.

     Пример:
     Четворката G = (V, T, P, S), където

       V ={<изречение>, <подлог>, <сказуемо>, <определение>,
            <местоимение>, <съществително>, <прилагателно>},
       T ={"този", "студент", "компютър", "лъв", "прекрасен",
            "добър", "красив", "силен", "е", "се явява"},
       P ={ <изречение>      ->  <подлог> <сказуемо> <определение>
            <подлог>         ->  <местоимение> <съществително>
            <определение>    ->  <прилагателно>
            <местоимение>    ->  "този"
            <съществително>  ->  "студент" | "компютър" | "лъв"
            <прилагателно>   ->  "прекрасен" | "добър" | "силен"
            <сказуемо>       ->  "е" | "се явява" }
       S = <изречение>,
     е КС-граматика.

   Задача 1: Да се дефинира отношение sentence(F), което да е истина, ако F е изречение, генерирано
             от описаната в примера граматика G.

   Решение:
           sentence(F) :- subject(A), verb(B), determination(C),
                          append(A, B, X), append(X, C, F).

           subject(A) :- pronoun(X), noun(Y), append(X, Y, A).

           determination(A) :- adjective(A).

           pronoun([this]).

           noun([student]).
           noun([computer]).
           noun([lion]).

           adjective([beautiful]).
           adjective([good]).
           adjective([strong]).

           verb([is]).
           verb([appears]).

   Дефинираното в тази задача отношението sentence има недостатъка, че от него не може лесно да се
   възстанови КС-граматика G, която то реализира.

   Задача 2: Да се дефинира ново отношение sentence, без да се използва отношението append.

   Решение: Ще добавим още един аргумент отношението subject(A, B) е истина, ако е началото на
   списъка А от анализирани думи стои подлог, след който е списъкът В. Освен това ще използваме
   отношението cons, дефинирано по следния начин:
                                                  cons([A|B], A, B).
   и намиращо главата и опашката на списък.
           Тогава програмата има вида:
           
           sentence(A, B) :- subject(A, A1), verb(A1, A2),
                             determination(A2, B).

           subject(A, B) :- pronoun(A, A1), noun(A1, B).

           determination(A, B) :- adjective(A, B).

           pronoun(A, B) :- cons(A, this, B).
                 
           noun(A, B) :- cons(A, student, B).
           noun(A, B) :- cons(A, computer, B).
           noun(A, B) :- cons(A, lion, B).

           adjective(A, B) :- cons(A, beautiful, B).
           adjective(A, B) :- cons(A, good, B).
           adjective(A, B) :- cons(A, strong, B).

           verb(A, B) :- cons(A, is, B).
           verb(A, B) :- cons(A, appears, B).