Синтез цифровых автоматов. Захаров Н.Г - 33 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

32
→ (q
1
, γ
1
), ..., (q
m
, γ
m
), причем γ = z β, γ′ = γ
i
β, q′ = q
i
для некоторого 1 ≤ i ≤ m
(z ∈V
м
, β
∈V
м
*
).
Говорят, что магазинный автомат переходит из состояния (q, γ) в состояние
(q′, γ′) и обозначают это следующим образом:
а : (q, γ) (q′, γ′).
Вводится и такое обозначение:
а
1
... a
n
: (q, γ)
*
(q′, γ′), если справедливо, что:
a
i
: (q
i
, γ
i
) (q
i+1
, γ
i+1
), 1 ≤ i ≤ n,
где a
i
∈ V, γ
i
= γ
1
, γ
2
,..., γ
n+1
= γ′∈V
м
* ; q
i
= q
1
, ..., q
n+1
= q′∈ Q.
2.4.2. Бесконтекстные (контекстно-свободные) языки
Существует два способа определения языка, допускаемого магазинным автома-
том. Согласно первому способу считается, что входная цепочка α ∈ V* принадлежит
языку L
1
(M) тогда, когда после просмотра последнего символа, входящего в эту це-
почку, в магазине автомата М будет находиться пустая цепочка ε. То есть:
L
1
(M) = { α | α : (q
0
, z
0
)
*
(q, ε)}, где q ∈ Q.
Согласно второму способу, считается, что входная цепочка принадлежит языку
L
2
(M) тогда, когда после просмотра последнего символа, входящего в эту цепочку,
автомат М окажется в одном из своих заключительных состояний. Другими словами,
L
2
(M) = { α | α : (q
0
, z
0
)
*
(q
f
, γ)}, где γ∈V
м
* , q
f
∈ F.
Доказано, что множество языков, допускаемых произвольными магазинными
автоматами согласно первому способу, совпадает с множеством языков, допускаемых
согласно второму способу.
Доказано также, что если L(G
2
) – бесконтекстный язык, порождаемый грамма-
тикой G
2
= (V
N
, V
T
, P, S), являющейся формой произвольной бесконтекстной грамма-
тики G, то существует недетерминированный магазинный автомат М, такой, что
L
1
(M) = L(G
2
). При этом
М = (V, Q, V
м
, δ, q
0
, z
0
, 0),
где V = V
T
; Q = {q
0
}; V
м
= V
N
; z
0
= S, а для каждого правила G
2
вида А → а α, а ∈V
Т
,
α ∈V
N
* строится команда отображения δ:
(q
0
, а, А) → (q
0
, α).
Аналогично, для любого недетерминированного магазинного автомата М, до-
пускающего язык L
1
(M), можно построить бесконтекстную грамматику G такую, что
L(G) = L
1
(M).
Если для конечных автоматов детерминированные и недетерминированные мо-
дели эквивалентны соответствующему классу допускаемых языков, то этого нельзя
сказать в отношении магазинных автоматов.
Детерминированные автоматы с магазинной памятью допускают лишь некото-
рое подмножество бесконтекстных языков, которые называют детерминированными
бесконтекстными языками.

Страницы