2. Алфавит (словарь)

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

Например, алфавит A = {a, b, c, +, !} содержит 5 букв;

алфавит B = {00, 01, 10, 11} одержит 4 буквы, каждая из которых состоит из двух символов.

2.1. Цепочка (слово).

Конечная последовательность символов (букв) алфавита называется цепочкой (словом) в этом алфавите.

Пустая цепочка – это цепочка, которая не содержит ни одного символа (для обозначения используется символы ε или $).

Длина цепочки (слова) – число символов (букв), входящих в цепочку (слово).

Например, слово a=ab+!c в алфавите A имеет длину l(a) = 5 или | а |=5;

слово b=00110010 в алфавите B имеет длину l(b) = 4;

если α = abcdefg, то длина α равна 7 — l(α)=7 или |α|=7;

длина ε равна 0 — l(ε)=0 или |ε|=0.

Конкатенация (сцепление) цепочек – это цепочка αβ, если α и β – цепочки.

Если α = ab и β = cd, то αβ = abcd

Для любой цепочки α всегда αε = εα = α.

Обращение (реверс) цепочки α – это цепочка α^R, символы которой записаны в обратном порядке.

Если α = abcdef, то α^R = fedcba

Для пустой цепочки: ε = ε^R.

Cтепень цепочки α – это конкатенация n цепочек α:

α⁰ = ε;

αⁿ = αα^n-1 = α^n-1α

2.2. Язык.

Язык в некотором алфавите – это подмножество цепочек конечной длины в этом алфавите.

Если задан алфавит A, то существует A^* – множество всевозможных цепочек, которые могут быть построены из букв алфавита A; предполагается, что пустая цепочка (ε или $) также входит в множество A^*.

Пусть V^* – множество, содержащее все цепочки в алфавите V, включая пустую цепочку ε, тогда, если V={0,1}, то V^* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}

Таким образом, каждый язык в алфавите V является подмножеством множества V^*.

3. Формальная порождающая грамматика

3.1. Грамматика, правила, цепочки.

Порождающая грамматика (грамматика Хомского) – один из видов формальной грамматики.

Порождающая грамматика есть упорядоченная четверка

G = (T, N, S, P)

где T – конечное множество терминальных (основных) символов (терминалов) – основной алфавит

N – множество нетерминалов – вспомогательных символов

T и N – не пересекающиеся конечные множества

S – символ из N, называемый начальным

Р – конечное подмножество множества, называемого множеством правил, которое описывает процесс порождения цепочек языка

Элемент p_i = (, ) множества Р называется правилом (продукцией)

 или->

Это означает, что цепочка  порождает цепочку  (из цепочки  выводится цепочка), ,  – цепочки, состоящие из терминалов и нетерминалов.

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую.

Обозначения для описания абстрактных языков:

• терминалы: буквы a, b, c, d или цифры 0, 1, ..., 9;

• нетерминалы: буквы A, B, C, D, S (нетерминал S – это начальный символ грамматики);

• отдельные терминалы или нетерминалы: буквы U, V, ..., Z;

• цепочки терминалов и нетерминалов:, , ...;

• цепочки терминалов: u, v, w, x, y, z;

• пустая цепочка (не содержащая ни одного символа) – знак ;

• порождает (есть по определению): знак , который отделяет левую часть правила от правой.

Обозначения определяют некоторый язык, предназначенный для описания правил построения цепочек, а значит, для описания других языков. Язык, предназначенный для описания другого языка, называется метаязыком.

Терминальной цепочкой, порождаемой грамматикой G, называется выводимая цепочка грамматики G, не содержащая нетерминалов.

Язык, порождаемый грамматикой, и сентенциальная форма в грамматике

Язык L(G), порождаемый грамматикой G, – это множество терминальных цепочек, порождаемых грамматикой G. Таким образом, L(G) – это все цепочки в алфавите T, которые выводимы из S (начальный символ) с помощью P (правила).

Цепочка α  (T U N)^*, для которой S  α, называется сентенциальной формой в грамматике G = (T, N, S, P).

Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Примеры грамматик

Грамматика, порождающая язык {0ⁿ1ⁿ | n≥0} имеет вид: G₀= ({0,1}, {S}, S, P)

T N S P

где P = {S→0S1, S→ε}.

Грамматика, порождающая язык {a^mbⁿ | m,n ≥ 0} имеет вид: G₁= ({a,b}, {S,A,B}, S, P)

T N S P

где набор правил определяется следующим образом:

P = {S→AB, A→aA, A→ε, B→bB, B→ε}

Понятие выводимости

Отношение _G непосредственного вывода на множестве (T  N)* – _G означает, что  непосредственно выводима из  для грамматики G = (T, N, P, S), т. е, если  – цепочка из множества (T  N)* и   – правило из Р, то _G

Транзитивное замыкание отношения _G⁺ (нетривиальный вывод за один и более шагов) — _G⁺ означает, что  выводима из нетривиальным образом (возможно за несколько шагов).

Рефлексивное и транзитивное замыкание отношения _G^* (вывод за нуль и более шагов) — _G^* означает, что выводима из .

Пусть ^k k-я степень отношения , тогда, если ^k, то существует последовательность ₀₁₂₃ ... _k из к+1 цепочек:

 =₀, ₁, ... _{i -1} _i,, 1 ≤ i ≤ k и _k = 

Выводы для грамматики G1 = ({0, 1}, {A, S}, S, P):

Т N S P

S  0A1  00A11  0011 — S порождает ...

S ¹ 0A1; S ² 00A11; S ³ 0011 – i-тая степень отношения

S ⁺ 0A1; S ⁺ 00A11; S ⁺ 0011 – транзитивное замыкание отношения

S ^* S; S ^* 0A1; S ^* 00A11; S ^* 0011 – рефлексивное и транзитивное замыкание отношения

где 0011  L(G1) – принадлежит языку L грамматики G1