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

UptoLike

ВУЗ: 

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

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

Рубрика: 

81
Пояснение. Цепочки w, составляющие одну пару, одинаковы.
I-5.6. Построить магазинный автомат, распознающий язык
L =
{ ww
R
| w∈{0, 1}
*
}.
Пояснение. w
R
обозначает инвертированную цепочку w.
I-5.7. Построить детерминированный магазинный автомат, распознающий
язык L =
{ wcw
R
| w∈{0, 1}
*
}.
I-5.8. Построить магазинные автоматы, распознающие следующие языки
при конечном состоянии:
a)
{w | w∈{0, 1}
*
, #
0
w = #
1
w}
b)
{a
n
b
m
| n ≤ m ≤ 2n}
c) Язык, порождаемый грамматикой
G = ({S, A}, {a, b}, {S → aAA, A → bS, A → aS, A → a }, S)
d) Язык арифметических выражений.
I-5.9. Построить грамматику языка N(M), где
M = ({q
0
, q
1
}, {0, 1}, {Z
0
, X}, δ, q
0
, Z
0
, ∅),
I- 5.10. Пусть L = N(M) для некоторого pda. Показать, что L = T(M
1
) для
некоторого pda с двумя состояниями.
I-5.11. Пусть L = T(M) для некоторого pda. Показать, что L = T(M
1
) для
некоторого pda M
1
с двумя состояниями. При каких условиях L = T(M
1
) для
некоторого pda M
1
с одним состоянием?
I-5.12. Пусть L = N(M) для некоторого pda. Показать, что L = N(M
1
) для
некоторого pda M
1
= (Q, Σ, Γ, δ, q
0
, Z
0
, F), где δ(q, ε, Z) = ∅ для всех q∈Q и Z∈Γ.

Страницы