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

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

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

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

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

A = {a, b, c, +, !}

B = {00, 01, 10, 11}

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

a=ab++c

l(a) = 5

b=00110010

l (b) = 4.

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

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

V_т

терминальный алфавит

терминальными символами

;

цепочки порождаемые грамматикой

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

 - начальный символ грамматики  О 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_n.

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

L( Г ) = {v О V_т^* | Ю*v }

Пред.Страница

След.Страница

Раздел

Содержание