К какому классу грамматик Хомского она относится

Грамматика:
S→ASB | ε
A→aAS | a | aEb
B→SbS | A | bb | ε
C→cC | EdA
E→cE | BdC
Грамматика относится ко классу грамматик Хомского 2 – классу контекстно-свободных.
Терминальные цепочки, порождаемые грамматикой:
SASBaSBaBaSBS=aASBBSaaSBBS=aaBBSaaBSaabS
aabASBaabaSBaabaBaaba.
SASBaSBaBaSbSabSabASBabaSBabaBababb.
SASBaSBaASBBaaSBBaaBBaaBaaAaaa.
Более простая (узкая) эквивалентная грамматика без нетерминальных символов C и E, не порождающих терминальных цепочек:
S→ASB | ε
A→aAS | a
B→SbS | A | bb | ε
Исходная грамматика в виде диаграмм Вирта:
2. Грамматика:
S→A | SA | SB
A→a
B→b
Грамматика относится к 2 классу грамматик Хомского – контекстно-свободные грамматики (т.к. в левой части правила встречается один нетерминальный символ, а в правой больше одного нетерминального).
Грамматика порождает язык цепочек из a и b, начинающихся с a.
Грамматика не является грамматикой типа, 3 – регулярные грамматики, однако существует регулярное выражение, описывающее тот же язык:
R = a(a+b)*.
3. Регулярная грамматика, обеспечивающая формирование правильных комбинаций шифра сейфа:
<combination>→A<A1> | B<B1> | C<C1> | … | 0<01> | … | 9<91>
<A1>→A<A2> | B<A2> | C<A2> | … | 0<A2> | … | 9<A2>
<B1>→ A<B2> | B<B2> | C<B2> | … | 0<B2> | … | 9<B2>
…
<91>→ A<92> | B<92> | C<92> | … | 0<92> | … | 9<92>
<A2>→A<A3> | B<A3> | C<A3> | … | 0<A3> | … | 9<A3>
<B2>→ A<B3> | B<B3> | C<B3> | … | 0<B3> | … | 9<B3>
…
<92>→ A<93> | B<93> | C<93> | … | 0<93> | … | 9<93>
<A3>→B | C | … | 0 | … | 9
<B3>→ A | C | … | 0 | … | 9
…
<93>→ A | B | C | … | 0 | … | 8
где нетерминалы A1…91 – обозначают уже введенную первую цифру комбинации, нетерминалы A2…92 – обозначают уже введенную вторую цифру комбинации, нетерминалы A3…93 – обозначают уже введенную третью цифру комбинации.
4. Грамматика:
S→aQb | accb
Q→cSc
Дерево вывода терминальной цепочки acacaccbcbcb (правосторонний вывод, восходящий распознаватель):
Правосторонний вывод:
S→aQb→acScb→acaQbcb→acacScbcb→acacaccbcbcb
S
Q
S
Q
S
a c a c a c c b c b c b
5 . Грамматика, которая позволяет порождать цепочки из 0 или 1 с неравным количеством 0 и 1:
G({0, 1},{S, C, D, E, F},P,S), где P:
S→0CS | 0F | 0 | 1DS | 1E | 1
C→0CC | 1
D→1DD | 0
E→1DE | 1D | 1E | 1
F→0CF | 0C | 0F | 0
Язык и грамматика не являются регулярными, эквивалентного конечного автомата не существует (в конечном автомате отсутствует память, подсчитать количество 0 или 1 для сравнения можно только вводя соответствующее количеству нулей (единиц) в цепочке число состояний, следовательно, для цепочек произвольной длины потребуется бесконечное количество состояний, что противоречит определению конечного автомата).
Блок-схема алгоритма формирования правильных цепочек языка (с использованием внешней памяти в виде переменной balance: balance > 0, если |0| > |1|, balance < 0, если |0| < |1| и balance = 0, если |0| = |1|):
Т.к. алгоритм не имеет эквивалентного конечного автомата, описана конфигурация абстрактного «автомата», реализующего алгоритм: (<непрочитанная_часть_цепочки>,<значение_переменной_balance>)
Цепочка 010
(010,balance=0) ├─ (10,balance=1) ├─ (0,balance=0) ├─ (ε,balance=1) – цепочка принята.
Цепочка 0011
(0011,balance=0) ├─ (011,balance=1) ├─ (11,balance=2)
 ├─ (1,balance=1) ├─ (ε,balance=0) – balance == 0, цепочка не принята.
Цепочка 01110
(01110,balance=0) ├─ (1110,balance=1) ├─ (110,balance=0)
 ├─ (10,balance=-1) ├─ (0,balance=-2) ├─ (ε,balance=-1) – цепочка принята.
МПА, допускающий по опустошению стека:
M({q0,q1,q2,q3,q4}, {0,1}, {0,1,Z}, δ, q0, {q4}), где
δ(q0,0,Z)={(q1,0Z)}
δ(q0,1,Z)={(q2,1Z)}
δ(q1,0,Z)={(q1,0Z)}
δ(q1,0,0)={(q1,00)}
δ(q1,1,Z)={(q2,1Z)}
δ(q1,1,0)={(q1,ε)}
δ(q1,ε,0)={(q3,ε)}
δ(q2,1,Z)={(q2,1Z)}
δ(q2,1,1)={(q2,11)}
δ(q2,0,Z)={(q1,0Z)}
δ(q2,0,1)={(q2,ε)}
δ(q2,ε,1)={(q3,ε)}
δ(q3,ε,0)={(q3,ε)}
δ(q3,ε,1)={(q3,ε)}
δ(q3,ε,Z)={(q4,ε)}
Цепочка 010
(q0,010,Z) ├─ (q1,10,0Z) ├─ (q1,0,Z) ├─ (q1,ε,0Z) ├─ (q3,ε,Z) ├─ (q4,ε,ε) – стек пуст, цепочка принята.
Цепочка 0011
(q0,0011,Z) ├─ (q1,011,0Z) ├─ (q1,11,00Z) ├─ (q1,1,0Z) ├─ (q1,ε,Z) –состояние не конечное, стек не пуст, цепочка не принята.
Цепочка 01110
(q0,01110,Z) ├─ (q1,1110,0Z) ├─ (q1,110,Z) ├─ (q2,10,1Z) ├─ (q2,0,11Z)  ├─ (q2,ε,1Z)  ├─ (q3,ε,Z)  ├─ (q4,ε,ε) – стек пуст, цепочка принята.
Машина Тьюринга, допускающая заданный язык:
MT = {Q, Σ, Γ, δ, q0, B, F}, где:
- Q = {q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13} – конечное множество состояний управляющего блока.
- Σ = {0, 1} – конечный алфавит входных символов.
- Γ = {0, 1, =, □}– конечный алфавит ленточных символов.
- q0 – состояние МТ, в котором она находится в начале работы.
- B = □ – пустой символ (или пробел)