Языки и трансляции. Мартыненко Б.К. - 81 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

80
Теперь определим правило для нетерминала [q
0
Zq
1
] из правой части (0.2)
по движению (1):
(1.3) [q
0
Zq
1
] → 0[q
0
Xq
0
][q
0
Zq
1
]
(1.4) [q
0
Zq
1
] → 0[q
0
Xq
1
][q
1
Zq
1
]
Правило (1.3) излишне, так как нетерминалы в правой части этого правила
непродуктивные.
Правило (1.4) даёт основание считать R множеством нетерминалов не
только продуктивных, но и достижимых.
Добавим правила для нетерминала [q
0
Xq
1
] из правой части (1.4), исходя из
движения (2):
(2.1) [q
0
Xq
1
] → 0[q
0
Xq
0
][q
0
Xq
1
],
(2.2) [q
0
Xq
1
] → 0[q
0
Xq
1
][q
1
Xq
1
].
Поскольку R = {[q
0
Xq
1
], [q
1
Xq
1
], [q
1
Zq
1
]}, то правило (2.1) излишне.
Правило (2.2) не даёт ничего для пополнения множества R: всё нетерминалы в
правой части уже находится в R.
Теперь определим правило для нетерминала [q
1
Xq
1
] из правой части (2.2)
по движению (2):
(2.3) [q
1
Xq
1
] → 0[q
1
Xq
0
][q
0
Xq
1
]
(2.4) [q
1
Xq
1
] → 0[q
1
Xq
1
][q
1
Xq
1
]
Правило (2.3) излишне, так как нетерминал [q
1
Xq
0
] в правой части этого
правила непродуктивный.
Окончательно получаем следующее множество правил приведённой
грамматики:
(0.2) S → [q
0
Zq
1
].
(1.4) [q
0
Zq
1
] → 0[q
0
Xq
1
][q
1
Zq
1
]
(2.2) [q
0
Xq
1
] → 0[q
0
Xq
1
][q
1
Xq
1
]
(2.4) [q
1
Xq
1
] → 0[q
1
Xq
1
][q
1
Xq
1
]
(4) [q
0
Xq
1
] → 1, (5) [q
1
Xq
1
] → 1
(6) [q
1
Xq
1
] → ε, (7) [q
1
Zq
1
] → ε
Упражнения
I-5.1. Является ли pda в примере 5.1 детерминированным? Обоснуйте ваш
ответ.
I-5.2. Почему в примере 5.3 нет ни одного правила для нетерминала [q
1
X q
0
]?
I-5.3. Дана cfg G = (V
N
, V
T
, P, S), где V
N
={E}, V
Т
={a, +,
*
},
P = {(1) E → +EE, (2) E →
*
EE, (3) E → a}.
Построить магазинный автомат, распознающий L = L(G).
I-5.4. Построить cfg, порождающую язык, который распознаётся магазин-
ным автоматом, построенным в упр. I-5.3. Доказать, что эти две грамматики
эквивалентны.
I-5.5. Построить магазинный автомат, распознающий язык
L = { (ww)
+
| w = 1
n
0, n > 0}.

Страницы