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

UptoLike

ВУЗ: 

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

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

Рубрика: 

146
Тогда по построению схемы T существует правило [qZp] → x ,y ∈R, с
помощью которого немедленно получаем: ([qZp], [qZp]) (x, y).
Индукционная гипотеза. Предположим, что утверждение I выполняется
для всех переходов между конфигурациями за число движений l ≤ n (n ≤ 1).
Индукционный переход. Докажем, что тогда утверждение I
справедливо и для l = n +1.
Итак, пусть (q, x, Z, ε)
(p, ε, ε, y). Рассмотрим этот переход подробнее.
В общем случае первое движение имеет вид
(q, x, Z, ε) = (q, ax′, Z, ε) (q
1
, x′, Z
1
Z
2
…Z
m
, y
0
). (1.10)
Затем следуют дальнейшие движения:
(q
1
,x
′
,Z
1
Z
2
…Z
m
, y
0
)=(q
1
, x
1
x
2
…x
m
,Z
1
…Z
m
, y
0
)
(q
2
, x
2
…x
m
, Z
2
…Z
m
, y
0
y
1
)
…
…
(q
m+1
, ε, ε, y
0
y
1
y
2
…y
m
)=(p, ε, ε, y).
Здесь a
∈Σ∪{ε}, x = ax
1
x
2
…x
m
, y = y
0
y
1
y
2
…y
m
, причём
(qi,xi, Zi,
ε)
(q
i + 1
, ε, ε,y
i
), i =1,2,…, m; l
i
≤ n; q
m + 1
= p. (1.11)
Первое движение (1.10) существует потому, что (q
1
,Z
1
…Z
m
, y
0
)∈δ(q, a, Z),
следовательно, по способу построения правил схемы в ней имеется правило
[qZp] → a[q
1
Z
1
q
2
][q
2
Z
2
q
3
]…[q
m
Z
m
q
m + 1
], y
0
[q
1
Z
1
q
2
][q
2
Z
2
q
3
]…[q
m
Z
m
q
m + 1
], (1.12)
в обозначениях нетерминалов которого участвуют те состояния, по которым
проходил pdt P. Из последующих движений (1.12) согласно индукционной
гипотезе следует существование выводов
([q
i
Z
i
q
i + 1
], [q
i
Z
i
q
i + 1
])
*
T
⇒
(x
i
, y
i
), i = 1,2,…, m. (1.13)
Из (1.12) и (1.13) можно выстроить требуемый вывод:
([qZp], [qZp]) (a[q
1
Z
1
q
2
]…[q
m
Z
m
q
m +1
], y
0
[q
1
Z
1
q
2
]…[q
m
Z
m
q
m +1
])
(ax
1
x
2
…x
m
, y
0
y
1
…y
m
) = (x, y).
II. Индукцией по длине l вывода докажем теперь обратное утверждение:
если ([qZp], [qZp])
(x, y), то (q, x, Z, ε)
(p, ε, ε, y).
База. Пусть l = 1. Имеем ([qZp],[qZp]) (x, y). На единственном шаге этого
вывода использовано правило схемы [qZp]
→ x,y, которое обязано своим
происхождением тому, что (p,
ε,y) ∈δ(q, x, Z), где x ∈Σ∪{ε}, y ∈∆
*
, а тогда
(q,x,Z,ε)
(p,ε,ε,y).
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех выводов, длина которых не превосходит n (0 ≤ n ≤ 1).
Индукционный переход. Докажем аналогичное утверждение для
выводов длиной l = n + 1. Пусть
([qZp], [qZp]) (a[q
1
Z
1
q
2
]…[q
m
Z
m
q
m + 1
],y
0
[q
1
Z
1
q
2
]…[q
m
Z
m
q
m +1
])
(x, y). (1.14)
Из (1.14) следует, что существует правило
[qZp] → a[q
1
Z
1
q
2
]…[q
m
Z
m
q
m + 1
], y[q
1
Z
1
q
2
]…[q
m
Z
m
q
m +1
]∈R,
которое обязано своим происхождение тому, что
(q
1
,Z
1
…Z
m
, y)∈δ(q,a, Z). (1.15)
1n
P
+
−−−
P
−−
1
l
P
−
−
2
l
P
−−
m
l
P
−−
i
l
P
−−
*
P
−
−
P
−−
T
⇒
*
T
⇒
*
T
⇒
*
T
⇒
T
⇒
*
T
⇒
T
⇒
T
⇒

Страницы