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

UptoLike

ВУЗ: 

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

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

Рубрика: 

36
§ 3.4. Конечные автоматы
и языки типа 3
Теперь мы возвращаемся к связи языков, порождаемых грамматиками типа 3,
с множествами, которые принимаются конечными автоматами. Для удобства
рассуждений введём понятие
конфигурации конечного автомата.
Определение 3.8. Пусть M = (Q, Σ, δ, q
0
, F) — конечный автомат.
Конфигурацией конечного автомата M назовем состояние управления в паре с
непрочитанной частью входной цепочки.
Пусть (q, ax) — конфигурация fa M, где q∈ Q, a∈Σ, x∈Σ
*
, и пусть p = δ(q, a)
в случае, если
M — dfa, или p ∈ δ(q, a) в случае, когда M — ndfa. Тогда fa M
может перейти из конфигурации (
q, ax) в конфигурацию (p, x), и этот факт мы
будем записывать как (
q, ax) (p, x). Далее символом обозначается
рефлексивно-транзитивное замыкание этого отношения на множестве
конфи-
гураций.
Запись (q
0
, x) (p, ε), где p∈ F, равнозначна записи x∈T(M).
Теорема 3.5. Пусть G = (V
N
, V
T
, P, S) — грамматика типа 3. Тогда
существует конечный автомат M = (Q, Σ, δ, q
0
, F), такой, что T(M ) = L(G).
Доказательство. Построим ndfa
M, о котором идёт речь. В качестве
состояний возьмем нетерминалы грамматики
и ещё одно дополнительное
состояние
A∉V
N
. Итак, Q = V
N
∪ {A}. Начальное состояние автомата M есть S.
Если множество
P содержит правило S → ε, то F ={S, A}. В противном случае
F ={A}. Напомним, что начальный нетерминал S не будет появляться в правых
частях правил, если
S → ε∈P.
Включим
A в δ(B, a), если B → a ∈P. Кроме того, в δ(B, a) включим все
C∈V
N
,
такие, что B → aС ∈P. Положим δ(A, a) = ∅ для каждого a ∈V
T
.
Построенный автомат
M, принимая цепочку x, моделирует её вывод в
грамматике
G. Требуется показать, что T(M) = L(G).
I. Пусть
x = a
1
a
2
...a
n
и x∈L(G), n ≥ 1. Тогда существует вывод вида
S ⇒ a
1
A
1
⇒ a
1
a
2
A
2
⇒ ... ⇒ a
1
a
2
... a
n – 1
A
n –1
⇒ a
1
a
2
...a
n –1
a
n
,
где
A
1
,..., A
n –1
∈ V
N
. Очевидно, что в нём используются следующие правила:
S → a
1
A
1
, A
1
→ a
2
A
2
, ..., A
n –2
→ a
n –1
A
n –1
, A
n –1
→ a
n
∈ P.
По построению δ
A
1
∈δ(S, a
1
), A
2
∈δ(A
1
, a
2
), ..., A
n –1
∈δ(A
n –2
, a
n –1
), A∈δ(A
n –1
, a
n
).
Следовательно, существует последовательность конфигураций
(
S, a
1
a
2
...a
n
)
(A
1
, a
2
...a
n
)
... (A
n –1
, a
n
)
(A, ε),
причём
A∈F и потому x∈T(M). Если же x = ε, то x∈L(G), и поскольку в этом
случае (
S, ε) (S, ε), S∈F, то x∈T(M ).
II. Пусть теперь
x = a
1
a
2
...a
n
и x∈ T(M), n ≥ 1. Тогда существует последо-
вательность конфигураций вида
(
S, a
1
a
2
...a
n
) (A
1
, a
2
...a
n
) ... (A
n –1
, a
n
) (A, ε),
где
A∈F. Очевидно, что
A
1
∈δ(S, a
1
), A
2
∈δ(A
1
, a
2
), ..., A
n – 1
∈δ(A
n –2
, a
n –1
), A∈δ(A
n –1
, a
n
).
−
−
*
−−
*
−−
−−
−
−
−
−
−
−
*
−−
−−
−
−
−
−
−
−

Страницы