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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
Но это возможно лишь при условии, что существуют правила
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.
Используя их, легко построить вывод вида
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
= x,
т.е.
x∈L(G).
Если же
x = ε и x∈T(M), то (S, ε) (S, ε) и S∈F. Но это возможно, если
только существует правило
S →ε∈ P. А тогда S ⇒ε и x∈ L(G).
Что и требовалось доказать.
Теорема 3.6. Пусть M = (Q, Σ, δ, q
0
, F) — конечный автомат. Существует
грамматика G
типа 3, такая, что L(G) = T(M).
Доказательство.
Без потери общности можно считать, что M — dfa.
Построим грамматику G =(V
N
, V
T
, P, S), положив V
N
= Q, V
T
= Σ, S = q
0
,
P = {q → ap | δ(q, a) = p} ∪ {q → a | δ(q, a) = p и p∈ F}. Очевидно, что G —
грамматика типа 3.
I. Пусть
x∈T(M) и |x| >0. Покажем, что x∈L(G).
Предположим, что
x = a
1
a
2
...a
n
, n >0. Существует последовательность кон-
фигураций автомата
M: (q
0
, a
1
a
2
...a
n
)
(q
1
, a
2
...a
n
)
...
(q
n –1
, a
n
)
(q
n
, ε),
причём
q
n
∈F. Соответственно δ(q
0
, a
1
) = q
1
, δ(q
1
, a
2
) = q
2
,..., δ(q
n –1
, a
n
) = q
n
. По
построению в множестве правил
P существуют правила вида q
i
→ a
i +1
q
i +1
(i =0,
1,...,
n –1) и правило q
n – 1
→ a
n
. С их помощью можно построить вывод
q
0
⇒ a
1
q
1
⇒ a
1
a
2
q
2
⇒ ... ⇒ a
1
a
2
...a
n –1
q
n –1
⇒ a
1
a
2
...a
n
.
А это значит, что
x∈L(G).
II. Пусть
x∈L(G) и |x| >0. Покажем, что x∈T(M).
Предположим, что
x = a
1
a
2
...a
n
, n >0. Существует вывод вида
q
0
⇒ a
1
q
1
⇒ a
1
a
2
q
2
⇒ ... ⇒ a
1
a
2
...a
n –1
q
n –1
⇒ a
1
a
2
...a
n
.
Соответственно существуют правила
q
i
→ a
i +1
q
i +1
(i = 0, 1,..., n –1) и
правило
q
n –1
→ a
n
. Очевидно, что они обязаны своим существованием тому, что
δ(
q
i
, a
i +1
) = q
i +1
(i = 0, 1,..., n –1) и q
n
∈F. А тогда существует последова-
тельность конфигураций fa
M вида
(
q
0
, a
1
a
2
...a
n
) (q
1
, a
2
... a
n
) ... (q
n –1
, a
n
) (q
n
, ε),
причём
q
n
∈ F. Это значит, что x∈ T(M).
Если
q
0
∉ F, то ε∉T(M) и L(G) = T(M). Если q
0
∈ F, то ε ∈ T(M). В этом случае
L(G) = T(M ) \ {ε}. По теореме 2.1 мы можем получить из G новую грамматику
G
1
типа 3, такую, что L(G
1
) = L(G)∪ {ε} = T(M). Что и требовалось доказать.
Пример 3.4. Рассмотрим грамматику типа 3 G =({S, B}, {0, 1}, P, S), где
P = {S → 0B, B → 0B, B → 1S, B → 0}. Мы можем построить ndfa
M
= ({S, B, A}, {0, 1}, δ, S, {A}), где δ определяется следующим образом:
1) δ(
S,0) = {B},
2) δ(
S,1) = ∅,
3) δ(
B,0) = {B, A}, 4) δ(B,1) = {S},
5) δ(
A,0) = ∅, 6) δ(A,1) = ∅.
По теореме 3.5
T(M ) = L(G), в чём легко убедиться и непосредственно.
−−
−
−
−
−
−
−
−
−
−
−
−
−
−−
*
−
−

Страницы