- •2. Классификация грамматик и языков
- •Иерархия Хомского
- •Примеры:
- •Соотношения между типами грамматик
- •Соотношения между типами языков
- •Вывод цепочек в грамматиках, неоднозначность грамматик и языков
- •Преобразования грамматик, нормальные формы грамматик
- •Алгоритмы перебор и методы его сокращения Перебор с возвратом (Общая схема)
- •Задача о лабиринте
- •Задача о парламенте
- •2.1.7. Задача о коммивояжере (перебор вариантов)
- •Задача о парламенте
2. Классификация грамматик и языков
Формальные грамматики можно классифицировать по типу существующих в них правил вывода.
Грамматика G называется неукорачивающей грамматикой, если каждое правило из R имеет вид , где V+, V+ и || ||.
Грамматика G называется укорачивающей грамматикой, если каждое правило из R имеет вид , где V+, V*.
Иерархия Хомского
T0: Грамматика G называется грамматикой типа 0 или рекурсивной грамматикой, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики – #).
T1: Грамматика G называется грамматикой типа 1 или контекстно-зависимой (КЗ) грамматикой, если каждое правило из R имеет вид , где = 1A2; = 12; A Vn; V+; 1, 2 V*.
Грамматику типа 1 можно определить как контекстно-зависимую или как неукорачивающую. Классы КЗ-грамматик и неукорачивающих грамматик эквивалентны. Доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.
Т2: Грамматика G называется грамматикой типа 1 или контекстно-свободной (КС) грамматикой, если каждое правило из R имеет вид A , где A Vn, V+ (для неукорачивающих КС-грамматик), или A Vn, 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) = {a2 bn2 – 1 | n 1}.
Грамматика G и язык L типа 1
Правила G:
S aSBC | abC
CB BC
bB bb
bC bc
cC cc
L(G) = {an bn cn, 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) = { | {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) не входит.