Классификация грамматик и языков
Формальные грамматики можно классифицировать по типу существующих в них правил вывода.
Грамматика G называется неукорачивающей грамматикой, если каждое правило из R
имеет вид a®b, где aÎ V+, bÎ V+ и |a| £ |b|.
Грамматика G называется укорачивающей грамматикой, если каждое правило из R
имеет вид a®b, где aÎ V+, bÎ V*.
Иерархия Хомского
T0: Грамматика G называется грамматикой типа 0 или рекурсивной грамматикой, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики – a¹ #).
T1: Грамматика G называется грамматикой типа 1 или контекстно-зависимой (КЗ) грамматикой, если каждое правило из R имеет
вид a®b, где a = x1Ax2; b = x1gx2; A Î Vn; gÎ V+; x1, x2Î V*.
Грамматику типа 1 можно определить как контекстно-зависимую или как неукорачивающую. Классы КЗ-грамматик и неукорачивающих грамматик эквивалентны. Доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.
Т2: Грамматика G называется грамматикой типа 1 или контекстно-свободной (КС) грамматикой, если каждое правило из R
имеет вид A ®b, где A Î Vn, bÎ V+ (для неукорачивающих КС-грамматик),
или AÎVn, bÎV* (для укорачивающих КС-грамматик).
Т3: Грамматика G называется грамматикой типа 3 или регулярной грамматикой, грамматикой с конечным числом состояний, если каждое правило из R
имеет вид A ®tB (A ®Bt) либо A ® t, где A, BÎVn, tÎVt.
Грамматика с правилами типа A ®tB является праволинейной.
Грамматика с правилами типа A ®Bt является леволинейной.
Множества языков, порождаемых праволинейными и леволинейными грамматиками, совпадают.
Язык L(G) является языком типа k, если его можно описать грамматикой типа k.
Примеры:
Грамматика G и язык L типа 0
Правила G:
S®aaCFD
F®AFB | AB
AB ®bBA
Ab®bA
AD ® D
Cb®bC
CB ® C
bCD® #
L(G) = {a2bn2 – 1 | n³ 1}.
Грамматика G и язык L типа 1
Правила G:
S®aSBC | abC
CB®BC
bB®bb
bC®bc
cC®cc
L(G) = {anbncn, n³ 1}
Грамматика G и язык L типа 2
Правила G:
S®aQb | accb
Q®cSc
L(G) = {(ac)n (cb)n, n> 0}
Грамматика G и язык L типа 3
Правила G:
S ® A | B
A ®a | Ba
B®b | Bb | Ab
L(G) = {w | wÎ {a,b}+, где нет двух рядом стоящих а}
3. Эквивалентность грамматик и языков,
соотношения между грамматиками и языками
Грамматики G1 и G2 эквивалентны, если L(G1) = L(G2).
Грамматики G1 и G2 сильноэквивалентны, если L(G1) = L(G2)
и грамматики приписывают цепочкам одинаковые структуры составляющих.
Пример:
G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)
R1: S® 0A1 R2: S® 0S1 | 01
A® 0A1
A® #
эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}.
Грамматики G1 и G2 условно эквивалентны, если L(G1) È {#} = L(G2) È {#}.
(если языки, ими порождаемые, отличаются не более, чем на #).
Пример:
G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)
R1: S® 0A1 R2: S® 0S1 | #
A® 0A1
A® #
условно эквивалентны, так как L(G1)={0n1n | n>0}, а L(G2)={0n1n | n³ 0}:
L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.
Соотношения между типами грамматик
(1) любая регулярная грамматика является КС-грамматикой;
(2) любая КС-грамматика является КЗ-грамматикой;
(3) любая КЗ-грамматика является грамматикой типа 0.
NB: УКС-грамматика с правилами вида A® #, не является КЗ-грамматикой.
Соотношения между типами языков
(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn| n>0}).
(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {anbncn| n>0}).
(3) каждый КЗ-язык является языком типа 0.
NB: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.
NB: Если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.
Пример:
КЗ-грамматика G1 = ({0, 1}, {A, S}, R1, S) и КС-грамматика G2 = ({0, 1}, {S}, R2, S),
где
R1: S ® 0A1 R2: S ® 0S1 | 01
0A ® 00A1
A® 01
описывают один и тот же язык L = L(G1) = L(G2) = {0n1n | n>0}.
Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык.
Эквивалентность грамматик и языков,
соотношения между грамматиками и языками
Грамматики G1 и G2 эквивалентны, если
L(G1) = L(G2).
Грамматики G1 и G2 сильноэквивалентны, если L(G1) = L(G2) и грамматики приписывают цепочкам одинаковые структуры составляющих.
Пример:
G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)
R1: S® 0A1 R2: S® 0S1 | 01
A® 0A1
A® #
эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}.
Вывод цепочек в грамматиках,
неоднозначность грамматик и языков
Цепочка aÎ V*, для которой S Þa, называется сентенциальной формой в грамматике G.
Вывод цепочки bÎ Vt* из S Î Vn в КС-грамматике G называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается изпредыдущей заменой самого левого нетерминального символа.
Вывод цепочки bÎ Vt* из S Î Vn в КС-грамматике G называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается изпредыдущей заменой самого правого нетерминального символа.
(КС – контекстно-свободная грамматика)
В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке.
Пример:
Для цепочки a+b+a в грамматике
G = ({a, b, +}, {S, T}, {S ® T | T+S; T ® a | b}, S)
можнопостроитьвыводы:
(1)S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a
(2) S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a
(3) S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a
Здесь (2) – левосторонний вывод, (3) – правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.
Существует удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.
Дерево называется деревом вывода (или деревом разбора) в грамматике G, если выполнены следующие условия:
(1) каждая вершина дерева помечена символом из множества (VnÈVtÈ #), при этом корень дерева помечен символом S; листья – символами из (VtÈ #);
(2) если вершина дерева помечена символом AÎVn, а ее непосредственные потомки – символами a1, a2,..., an, где каждое aiÎ (VtÈVn), то A®a1a2...an – правило вывода в этой грамматике;
(3) если вершина дерева помечена символом AÎVn, а ее единственный непосредственный потомок помечен символом #, то A® # – правило вывода в этой грамматике.
Пример дерева вывода для цепочки a+b+a в грамматике G:
S
T S
 |  |
T S
 |
T
 |
a + b + a
Грамматика G называется неоднозначной, если существует хотя бы одна цепочка aÎ L(G), для которой может быть построено два или более различных деревьев вывода (цепочка a имеет два или более разных левосторонних (или правосторонних) выводов).
В противном случае грамматика называется однозначной.
Язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.
Пример:
неоднозначная грамматика
G = ({if, then, else, a, b}, {S}, R, S),
где R = {S ® if b then S else S | if b then S | a}.
В этой грамматике для цепочки ifbthenifbthenaelsea можно построить два различных дерева вывода.
Однако это не означает, что язык L(G) обязательно неоднозначный.
Неоднозначность - это свойство грамматики, а не языка, поскольку для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.
В рассматриваемом примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и исправить грамматику G, то неоднозначность будет устранена:
S ® if b then S | if b then S’ else S | a
S’ ® if b then S’ else S’ | a
Некоторые виды правил вывода, которые приводят к неоднозначности:
(1)A ® AA | a
(2)A ®AaA | b
(3)A ®aA | Ab | g
(4)A ®aA | aAbA | g
Пример неоднозначного КС-языка:
L = {aibjck| i = j или j = k}.
Цепочки с i = j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j = k. Но тогда, по крайней мере, некоторые из цепочек с i = j = k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода.
Одна из грамматик, порождающих L, такова:
S ® AB | DC
A ®aA | #
B ®bBc | #
C®cC | #
D®aDb | #
Очевидно, что она неоднозначна.
Дерево вывода можно строить нисходящим либо восходящим способом.
При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, надо найти такое правило вывода, чтобы имеющиеся в нем терминальные символы “проектировались” на символы исходной цепочки.
Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.
Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.