Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 25 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

25
3) реализация эквивалентных преобразований грамматики, направленных
на удаление:
а) бесполезных символов;
б) недостижимых символов;
в) ε-правил;
г) цепных правил;
д) левой факторизации правил;
е) прямой левой рекурсии.
Варианты индивидуальных заданий представлены в таблице 4.1.
Таблица 4.1 – Варианты индивидуальных заданий к лабораторной работе
№ 4 и 5
Вариант Контекстно-свободная грамматика
1
G=({S, A, B, D, E}, {a, b, c, e}, P, S), где P:
1) S→AB |
ε
; 2) A→Aa | S | a; 3) B→bD | bS | b; 4) D→ccD; 5) E→eE |e.
2
G=({E, T, F, G, H}, {+, -, *, /, n, m, h}, P, E), где P:
1) E→T | E+T | E-T | ε; 2) T→F | F*T | F/T | ε; 3) F→G | Fn | n;
4) G→Gm; 5) H→Hh | h.
3
G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
.|)5
;)4;|)3|||)2;|)1
yaYaY
aXbX
g
T
g
T
p
a
T
p
aR
p
X
R
T
R
S
→
→→→→
4
G=({Q, A, B, C, D}, {a, b, c, d}, P, Q), где P:
dcD
dCc
C
a
A
b
A
a
A
Cb
A
B
acBacAQ
→
→→→→
)5
)4;||)3;||)2;||)1
5
G=({R, T, F, G, K}, {m, i, j, k, ^, ~, ⊥}, P, R), где P:
1) R→R~T⊥ | R^T⊥ | ε; 2) T→F | Fi | Fj | Gk | ε; 3) G→GkG;
4) K→Ki | Km | m.
6
G=({S, X, Y, Z, K}, {x, y, z, k, #, $}, P, S), где P:
1) S→X | Y | Z; 2) X→x#X | x#Y | ε; 3) Y→Yy$ |Yz$ | $ | ε; 4) Z→Zz$;
5) K→Kk$ | k$.
7
G=({S, L, M, P, N}, {n, m, l, p, @, ⊥}, V, S), где V:
1) S→@nL | @mM | P; 2) L→M | Ll⊥ | Lm⊥ |ε; 3) M→L | Mm | mm;
4) N→pN@ | @; 5) P→nmP.
8
G=({X, Y, Z, K, L}, {a, b, l, =, <, >, ∧, ∨, ¬}, V, X), где V:
1) X→Y | Y=Y | Y<Y | Y>Y | K; 2) Y→Y∧Z | Y∨ Z | ε; 3) Z→ ¬ a | ¬ b| ε;
4) K→ ¬ K; 5) L→ l | a | b.
9
G=({Q, A, B, C, D}, {0, 1, -}, P, Q), где P:
1) Q→01A | 01B | A; 2) A→ 0B1 | B | 1 | ε; 3) B→BA0 | B1 | C | ε; 
      3) реализация эквивалентных преобразований грамматики, направленных
на удаление:
            а) бесполезных символов;
            б) недостижимых символов;
            в) ε-правил;
            г) цепных правил;
            д) левой факторизации правил;
            е) прямой левой рекурсии.
      Варианты индивидуальных заданий представлены в таблице 4.1.
   Таблица 4.1 – Варианты индивидуальных заданий к лабораторной работе
№4и5

Вариант                         Контекстно-свободная грамматика
          G=({S, A, B, D, E}, {a, b, c, e}, P, S), где P:
   1
          1) S→AB | ε; 2) A→Aa | S | a; 3) B→bD | bS | b; 4) D→ccD; 5) E→eE |e.

          G=({E, T, F, G, H}, {+, -, *, /, n, m, h}, P, E), где P:
   2      1) E→T | E+T | E-T | ε; 2) T→F | F*T | F/T | ε; 3) F→G | Fn | n;
          4) G→Gm; 5) H→Hh | h.
          G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
   3      1) S → R | T ; 2) R → pX | paR | paT | ε 3) T → Tg | g ; 4) X → aXb;
          5) Y → aYa | y.
          G=({Q, A, B, C, D}, {a, b, c, d}, P, Q), где P:
   4      1) Q → acA | acB | ε ; 2) B → A | Cb | ε ; 3) A → Aa | Ab | a; 4) C → dCc
          5) D → dc
          G=({R, T, F, G, K}, {m, i, j, k, ^, ~, ⊥}, P, R), где P:
   5      1) R→R~T⊥ | R^T⊥ | ε; 2) T→F | Fi | Fj | Gk | ε; 3) G→GkG;
          4) K→Ki | Km | m.
          G=({S, X, Y, Z, K}, {x, y, z, k, #, $}, P, S), где P:
   6      1) S→X | Y | Z; 2) X→x#X | x#Y | ε; 3) Y→Yy$ |Yz$ | $ | ε; 4) Z→Zz$;
          5) K→Kk$ | k$.
          G=({S, L, M, P, N}, {n, m, l, p, @, ⊥}, V, S), где V:
   7      1) S→@nL | @mM | P; 2) L→M | Ll⊥ | Lm⊥ |ε; 3) M→L | Mm | mm;
          4) N→pN@ | @; 5) P→nmP.
          G=({X, Y, Z, K, L}, {a, b, l, =, <, >, ∧, ∨, ¬}, V, X), где V:
   8      1) X→Y | Y=Y | YY | K; 2) Y→Y∧Z | Y∨ Z | ε; 3) Z→ ¬ a | ¬ b| ε;
          4) K→ ¬ K; 5) L→ l | a | b.
          G=({Q, A, B, C, D}, {0, 1, -}, P, Q), где P:
   9
          1) Q→01A | 01B | A; 2) A→ 0B1 | B | 1 | ε; 3) B→BA0 | B1 | C | ε;

                                                                                  25

Страницы