Математическая логика и теория алгоритмов. Стенюшкина В.А. - 98 стр.

ко, они разделяются символом |, означающим «или». Имена конструкции за-
ключаются в угловые скобки <, >. В расширенном варианте НФБ используются
символы: [, ] – для необязательных элементов и т. д. Существенной чертой ме-
талингвистических форм является наличие в них рекурсий – явных и неявных.
       Пример – НФБ – описание десятичного числа:
       <десятичное число>: : = [±]<цифра>…
       <цифра>: : = 0/1/2/3/4/5/6/7/8/9.
       Многоточие в примере означает повторение элемента.

       6.2 Формальные языки и грамматики

         Формальным языком L над алфавитом А называется множество цепочек
символов этого алфавита.
         Если а1, а2, … ∈ А, то а1 … аn –цепочка длины n. Обозначения цепочек
α, β, ... . Цепочка β называется подцепочкой α, если α=γβδ, где γ, β тоже цепоч-
ки.      Цепочки       можно    рассматривать    как   элементы         множества
  *    0     1                 0                          1           n
А =А ∪А ∪…= ∪ n =0 A , где А ={λ}, λ - пустая цепочка, А =А, … , А =A× … ×A
                     ∞   n


(n раз). Множество непустых цепочек определяющихся как A+=A*\A0= ∪ ∞n =1 A n .
Длина цепочки α обозначатся через |α|, при этом |λ|=0. На множестве цепочек
определяется операция конкатенации. Обозначение: ⊕. Для двух цепочек α, β
конкатенация означает приписывание второй цепочки к первой. Например, если
α=ко, β=нец, то α⊕β=αβ=конец. При этом λα=αλ=α. Операция ⊕ ассоциатив-
на, но не коммутативна. Для записи повторяющихся символов можно исполь-
зовать верхний индекс. Например, xx=x2, xyxyx=(xy)2y=x(xy)2. Кроме того, мо-
жно писать x0 вместо λ, x1 вместо x.
         Формальной грамматикой называется формальное определение синтак-
тики языка. Существует два основных способа задания языка: с помощью по-
рождающей процедуры и с помощью распознающей процедуры.

       6.3 Порождающие грамматики

       Определение Формальной порождающей грамматикой называется чет-
вёрки П=, глее Т- конечное непустое множество символов, называ-
емых нетерминалами; S – начальный символ, называемый главным нетермина-
лом; P – конечное множество правил грамматики. Правила называются двумес-
тными отношениями вида ϕ→ψ, где ϕ,ψ - цепочки над алфавитом V=T∪N,
причём в левой части должен содержаться хотя бы один нетерминал ; → -
символ отношения – интерпретируется как «заменить ϕ на ψ».Здесь терминалы
будем обозначать через a,b,c, … , нетерминалы – A, B, C, … .Цепочка β называ-
ется непосредственно выводимой из цепочки α в грамматике G, если α=ξ1ϕ ξ2,
βα=ξ1ψ ξ2 и существует правило ϕ→ψ. Запись α⇒β.
       Цепочка β называется выводимой из цепочки α в грамматике G, если
либо α=β, либо существует последовательность цепочек α=ω0, ω1, … ωn=β та-