299
правок
Изменения
→Теоремы
{{В разработке}}
==Теоремы==
===Теорема 0===
{{Теорема
|id=t0
|about=0
|statement=Пусть <tex>P = (Q, Σ\Sigma, Γ\Gamma, δ\delta, q0q_0, Z0Z_0) </tex> — МП-автомат. Тогда существует КС- грамматика <tex>G</tex>, для которой <tex>L(G) = N(P)</tex>.
|proof=
Построим <tex>G = (V, \Sigma, R, S)</tex>, где V состоит из следующих переменных.
#Специальный стартовый символ <tex>S</tex>.
#Все символы вида <tex>[pXq]</tex>, где <tex>p</tex> и <tex>q</tex> — состояния из <tex>Q</tex>, а <tex>X</tex> — магазинный символ из <tex>\Gamma</tex>.<br>Грамматика <tex>G</tex> имеет следующие продукции:<br>а) продукции <tex>S \rightarrow [q0Z0p]</tex> для всех состояний <tex>p</tex>. Интуитивно символ вида <tex>[q0Z0p]</tex> предназначен для порождения всех тех цепочек <tex>w</tex>, которые приводят <tex>P</tex> к выталкиванию <tex>Z_0</tex> из магазина в процессе перехода из состояния <tex>q_0</tex> в состояние <tex>p</tex>. Таким образом, <tex>(q, w, Z_0) \vdash (q, \epsilon, \epsilon)</tex>. Эти продукции гласят, что стартовый символ <tex>S</tex> порождает все цепочки <tex>w</tex>, приводящие <tex>P</tex> к опустошению магазина после старта в начальной конфигурации;<br>б) пусть <tex>\delta(q,a,X)</tex> содержит пару <tex>(r,Y_1Y_2...Y_k)</tex>,где <tex>a</tex> есть либо символ из <tex>\Sigma</tex>, либо <tex>\epsilon</tex>, а <tex>k</tex> — некоторое неотрицательное число; при <tex>k = 0</tex> пара имеет вид <tex>(r, \epsilon)</tex>. Тогда для всех списков состояний <tex>r_1, r_2, ..., r_k</tex> в грамматике <tex>G</tex> есть продукция<br><tex>[qXrk] \rightarrow a[rY1r1][r1Y2r2]...[rk–1Ykrk]</tex>.
Она гласит, что один из путей выталкивания X и перехода из состояния q в состояние rk заключается в том, чтобы прочитать a (оно может быть равно ε), затем использовать некоторый вход для выталкивания Y1 из магазина с пере- ходом из состояния r в состояние r1, далее прочитать некоторый вход, вы- толкнуть Y2 и перейти из r1 в r2, и т.д.
Докажем корректность неформальной интерпретации переменных вида [qXp]:
[qXp] ⇒ w тогда и только тогда, когда (q, w, X) |− (p, ε, ε).
(Достаточность) Пусть (q, w, X) |− (p, ε, ε). Докажем, что [qXp] ⇒ w, используя ин-дукцию по числу переходов МП-автомата.
Базис. Один шаг. Пара (p, ε) должна быть в δ(q, w, X), и w есть либо одиночный символ, либо ε. Из построения G следует, что [qXp] → w является продукцией, поэто- му [qXp] ⇒ w.
*
Индукция. Предположим, что последовательность (q, w, X) |− (p, ε, ε) состоит из n
переходов, и n > 1. Первый переход должен иметь вид *
(q, w, X) |− (r0, X, Y1Y2...Yk) |− (p, ε, ε),
где w = aX для некоторого a, которое является либо символом из Σ, либо ε. Отсюда следу- ет, что пара (r0, Y1Y2...Yk) должна быть в δ(q, a, X). Кроме того, по построению G сущест- вует продукция [qXrk] → a[r0Y1r1][r1Y2r2]...[rk–1Ykrk], у которой rk = p и r1, r2, ..., rk–1 — не- которые состояния из Q.
На рис. 6.10 показано, что символы Y1, Y2, ..., Yk удаляются из магазина по очереди, и
для i = 1, 2, ..., k – 1 можно выбрать состояние pi, в котором находится МП-автомат при
удалении Yi. Пусть X = w1w2...wk, где wi — входная цепочка, которая прочитывается до *
удаления Yi из магазина. Тогда (ri–1, wi, Yi) |− (ri, ε, ε).
Поскольку ни одна из указанных последовательностей переходов не содержит более,
чем n переходов, к ним можно применить предположение индукции. Приходим к выво- *
ду, что [ri–1Yiri] ⇒ wi. Соберем эти порождения вместе.
[qXrk] ⇒ a[r0Y1r1][r1Y2r2]...[rk–1Ykrk] ⇒* aw1[r1Y2r2]...[rk–1Ykrk] ⇒*
aw1w2[r2Y3r3]...[rk–1Ykrk] ⇒* ...
aw1w2...wk = w
Здесь rk = p.
(Необходимость) Доказательство проводится индукцией по числу шагов в порождении. Базис. Один шаг. Тогда [qXp] → w должно быть продукцией. Единственная возмож-
ность для существования этой продукции — если в P есть переход, в котором X вытал- кивается, а состояние q меняется на p. Таким образом, пара (p, ε) должна быть в δ(q,a,X),иa=w.Нотогда(q,w,X) |− (p,ε,ε).
*
Индукция. Предположим, что [qXp] ⇒ w за n шагов, где n > 1. Рассмотрим подроб-
но первую выводимую цепочку, которая должна выглядеть следующим образом. *
[qXrk] ⇒ a[r0Y1r1][r1Y2r2]...[rk–1Ykrk] ⇒ w
Здесь rk = p. Эта продукция должна быть в грамматике, так как (r0, Y1Y2...Yk) есть в
δ(q, a, X).
Цепочку w можно разбить на w = aw1w2...wk так, что [ri–1Yiri] ⇒ wi для всех i = 1, 2, ...,
k – 1. По предположению индукции для всех этих i верно следующее утверждение. *
(ri–1, wi, Yi) |− (ri, ε, ε)
Используя теорему 6.5 для того, чтобы поместить нужные цепочки вокруг wi на входе и
под Yi в магазине, получим
(ri–1, wiwi+1...wk, YiYi+1...Yk) |− (ri, wi+1...wk, Yi+1...Yk).
Соберем все эти последовательности вместе и получим следующее порождение.
* (q, aw1w2...wk, X) |− (r0, w1w2...wk, Y1Y2...Yk) |−
***
(r1, w2w3...wk, Y2Y3...Yk) |− (r2, w3...wk, Y3...Yk) |− ... |− (rk, ε, ε)
* Поскольку rk = p, мы доказали, что (q, w, X) |− (p, ε, ε).
**
Завершим доказательство. S ⇒ w тогда и только тогда, когда [q0Zp0] ⇒ w для неко-
*
торого p в соответствии с построенными правилами для стартового символа S. Выше уже **
доказано, что [q0Zp0] ⇒ w тогда и только тогда, когда (q, w, Z0) |− (p, ε, ε), т.е. когда P
допускает w по пустому магазину. Таким образом, L(G) = N(P).
}}
===Теоремы1===
{{Теорема
|id=t1
