Пред.Страница  След.Страница   Раздел   Содержание

---

1.2. Определение формальной грамматики и языка

Изучение предмета начнем с определения первичных понятий.

1.2.1. Первичные понятия

Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем или алфавитом, а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Определение.  Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Число букв, входящих в слово, называется его длиной.

Например, слово в алфавите A a=ab++c имеет длину l(a) = 5, а слово в алфавите B b=00110010 имеет длину l (b) = 4.

Если задан алфавит A, то обозначим A^* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A^*.

Определение.  Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { V_т, V_A, <I> Î V_A, R }, 

где V_т - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой; 

V_A - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения; 

<I> - начальный символ грамматики <I> Î V_A.

R - множество правил вывода или порождающих правил вида a ® b , где aи b - цепочки , построенные из букв алфавита V_тÈ V_A, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е> ® . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е> ® $.

Чтобы установить правила построения цепочек, порождаемых грамматикой , введем следующие понятия.

Определение.  Пусть r = t ® g - правило грамматики Г и a = c't c" - цепочка символов, причем c', c" Î(Vт ÈV_A) ^*. Тогда цепочка b= c' g c " может быть получена из цепочки путем применения правила r (т.е. заменой в m цепочки t на g). В этом случае говорят, что цепочка b непосредственно выведена из цепочки a и обозначают a Þb . 

Определение.  Если задана совокупность цепочек W = ( v₀, v₁,...,v_n), таких что существует последовательность непосредственных выводов: 

v₀ Þ v₁, v₁ Þ v₂, ... ,v _n-1 Þv _n,

то такую последовательность называют выводом v_n из v₀ в грамматике Г и обозначают 

v ₀ Þ* v_n.

Определение.  Множество конечных цепочек терминального алфавита V_т грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L( Г). 

L( Г ) = {v Î V_т^* | <I> Þ*v }. 

---

Пред.Страница  След.Страница   Раздел   Содержание