Специальная математика. Соловьев А.Е. - 72 стр.

Рассмотрим примеры -редукции (в прикладной варианте записи)
(х.х + 2у)(а) = а + 2у

(у.х + 2у)(а) = х + 2а

(х.(у.х + 2у))(а)(b) = (у.а + 2у)(b) = a + 2b

(x.((y.xy)u))( v.v) = (y.(v.v)y)u = (v.v)u
(x.((y.xy)u))( v.v) = (x.xu)(v.v) = (v.v)u

(x.xx) (x.xx) = (x.xx) (x.xx) = (x.xx) (x.xx) =…

((x.x*3) (y.if y > 4 then e = 2 else x/2) (y.y>2)) (5) = 2*5 = 10

(n.(x.x-n))(2) = x.x-2

(f.2*f(8) – f(f(8)))(half) = 2*8/2 – (8/2)/2 = 6   (half – половина).




                              7. Формальные грамматики
                          7.1. Понятие формальной грамматики

 Формальная грамматика - это четверка G = , в которой
 VN - нетерминальный словарь (множество нетерминальных символов);
VT - терминальный словарь (множество терминальных символов ) ;
  P - множество грамматических правил;
  S  VN - начальный нетерминальный символ.
Метаязык - язык, с помощью которого описывается язык:
::= - есть по определению;
  | - “ исключающее или”;
  < ... > - внутри – один нетерминальный символ ;
  [ ] - необязательная часть;
   , - запятая – разделитель при перечислении.
Пример: Построим грамматику G1:
 <прог>::=<оп> | <оп>; <прог>
 <оп>::=<пер> := <выр>
 <пер>::=a | b | c
 <выр>::=<пер> | <пер> <зн> <выр>
 <зн>::= + | - | * | /

V = VN  VT - обобщенный словарь.
 V* - цепочка символов (строка, слово) из обобщенного словаря;
 V*N - цепочка символов (строка, слово) из нетерминального словаря;
V*T - цепочка символов (строка, слово) из терминального словаря.
  V - пустой символ, входит в обобщенный словарь.

Строка  непосредственно порождает строку  и обозначается:    ,

                                                — 72 —