Методические указания к лабораторным работам по курсу "Теория вычислительных процессов и структур". Домашова Д.В - 7 стр.

                 S



        T                    S

                     T           S

                                 T

        a        +   b +         a

     Рисунок 1.1 – Синтаксическое дерево цепочки а+b+c

     Будем изображать правило в соответствии с рисунком 1.2: S:=α1|α2|…|αn
                 S



       α1   α2       . . .           αn

     Рисунок 1.2 – Синтаксическое дерево

1.3 Классификация грамматик по Хомскому

      ТИП 0. Правила вывода на имеют ограничений.
      ТИП 1.Контекстно-зависимые (КЗ) грамматики - правила вывода
имеют вид:
      αUβ::=αχβ,
      U∈VN; α,χ,β - любые цепочки
      ТИП 2. Контекстно-свободные (КС) грамматики с правилами:
      U::= χ , U∈VN, - любая цепочка
      КС∈КЗ {если α,β=Λ }
      ТИП 3. Регулярные (Р) грамматики - все правила имеют вид
       N::=t или N::=Mt, N,M∈VN, t∈VT
       P∈KC∈KЗ∈ТИП0
 Определение. Язык называется языком типа К, если порождается
 грамматикой типа К
      Обозначения: малые латинские буквы - символы терминального
алфавита; большие латинские буквы - символы нетерминального алфавита;
греческие буквы - цепочки в алфавите ;
      Пример -
               S::=aSBC|Q


10