ДМП-автоматы и неоднознчность

Эта статья находится в разработке!

Теоремы

Теорема 0

Теорема (0):

Пусть [math]P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0)[/math] — МП-автомат. Тогда существует КС- грамматика [math]G[/math], для которой [math]L(G) = N(P)[/math].

Доказательство:

[math]\triangleright[/math]

Построим [math]G = (V, \Sigma, R, S)[/math], где V состоит из следующих переменных. Специальный стартовый символ [math]S[/math]. Все символы вида [math][pXq][/math], где [math]p[/math] и [math]q[/math] — состояния из [math]Q[/math], а [math]X[/math] — магазинный символ из [math]\Gamma[/math]. Грамматика [math]G[/math] имеет следующие продукции: продукции [math]S \rightarrow [q0Z0p][/math] для всех состояний [math]p[/math]. Интуитивно символ вида [math][q0Z0p][/math] предназначен для порождения всех тех цепочек [math]w[/math], которые приводят [math]P[/math] к выталкиванию [math]Z_0[/math] из магазина в процессе перехода из состояния [math]q_0[/math] в состояние [math]p[/math]. Таким образом, [math](q, w, Z_0) \vdash (q, \epsilon, \epsilon)[/math]. Эти продукции гласят, что стартовый символ [math]S[/math] порождает все цепочки [math]w[/math], приводящие [math]P[/math] к опустошению магазина после старта в начальной конфигурации; пусть [math]\delta(q,a,X)[/math] содержит пару [math](r,Y_1Y_2...Y_k)[/math],где [math]a[/math] есть либо символ из [math]\Sigma[/math], либо [math]\epsilon[/math], а [math]k[/math] — некоторое неотрицательное число; при [math]k = 0[/math] пара имеет вид [math](r, \epsilon)[/math]. Тогда для всех списков состояний [math]r_1, r_2, ..., r_k[/math] в грамматике [math]G[/math] есть продукция [math][qXr_k] \rightarrow a[rY_1r_1][r_1Y_2r_2]...[r_{k-1}Y_kr_k][/math]. Она гласит, что один из путей выталкивания [math]X[/math] и перехода из состояния [math]q[/math] в состояние [math]r_k[/math] заключается в том, чтобы прочитать [math]a[/math] (оно может быть равно [math]\epsilon[/math]), затем использовать некоторый вход для выталкивания [math]Y_1[/math] из магазина с переходом из состояния [math]r[/math] в состояние [math]r_1[/math], далее прочитать некоторый вход, вытолкнуть [math]Y_2[/math] и перейти из [math]r_1[/math] в [math]r_2[/math], и т.д. Докажем корректность неформальной интерпретации переменных вида [math][qXp][/math]: [math][qXp] \Rightarrow w[/math] тогда и только тогда, когда [math](q, w, X) \vdash (p, \epsilon, \epsilon)[/math]. (Достаточность) Пусть [math](q, w, X) \vdash (p, \epsilon, \epsilon)[/math]. Докажем, что [math][qXp] \Rightarrow w[/math], используя индукцию по числу переходов МП-автомата. Базис. Один шаг. Пара [math](p, \epsilon)[/math] должна быть в [math]\delta(q, w, X)[/math], и [math]w[/math] есть либо одиночный символ, либо [math]\epsilon[/math]. Из построения [math]G[/math] следует, что [math][qXp] \rightarrow w[/math] является продукцией, поэтому [math][qXp] \Rightarrow w[/math]. Индукция. Предположим, что последовательность [math](q, w, X) \vdash (p, \epsilon, \epsilon)[/math] состоит из [math]n[/math] переходов, и [math]n \gt 1[/math]. Первый переход должен иметь вид [math](q, w, X) \vdash (r_0, X, Y_1Y_2...Y_k) \vdash (p, \epsilon, \epsilon)[/math], где [math]w = aX[/math] для некоторого [math]a[/math], которое является либо символом из [math]\Sigma[/math], либо [math]\epsilon[/math]. Отсюда следу- ет, что пара (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)

[math]\triangleleft[/math]

Теоремы1

Теорема (1):

Если [math]L=N(P)[/math] для некоторого ДМП автомата [math]P[/math], то [math]L[/math] имеет однозначную КС-грамматику

Доказательство:

[math]\triangleright[/math]

Утверждаем, что конструкция теоремы 6.14 порождает однозначную КС-грамматику [math]G[/math], когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики [math]G[/math] достаточно показать, что она имеет уникальные левые порождения. Предположим, [math]P[/math] допускает [math]w[/math] по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении [math]w[/math] в [math]G[/math]. Правило автомата [math]P[/math], на основании которого применяется продукция, всегда одно. Но правило, скажем, [math]\delta(q, a, X) = \{(r, Y_1Y_2...Y_k)\}[/math], может порождать много продукций грамматики [math]G[/math], с различными состояниями в позициях, отражающих состояния [math]P[/math] после удаления каждого из [math]Y_1[/math], [math]Y_2[/math], ..., [math]Y_k[/math]. Однако, поскольку [math]P[/math] детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению [math]w[/math].

[math]\triangleleft[/math]

Теорема (2):

Если [math]L=L(P)[/math] для некоторого ДМП-автомата [math]P[/math], то [math]L[/math] имеет однозначную КС-грамматику

Доказательство:

[math]\triangleright[/math]

Пусть [math]\$[/math] будет “концевым маркером”, отсутствующим в цепочках языка [math]L[/math], и пусть [math]L` = L\$[/math]. Таким образом, цепочки языка [math]L`[/math] представляют собой цепочки из [math]L[/math], к которым дописан символ [math]\$[/math]. Тогда [math]L`[/math] имеет префиксное свойство, и [math]L` = N(P`)[/math] для некоторого ДМП-автомата [math]P`[/math]. По теореме 1 существует однозначная грамматика [math]G`[/math], порождающая язык [math]N(P`)[/math], т.е. [math]L`[/math]. Теперь по грамматике [math]G`[/math] построим [math]G[/math], для которой [math]L(G) = L[/math]. Для этого нужно лишь избавиться от маркера [math]\$[/math] в цепочках. Будем рассматривать [math]\$[/math] как переменную грамматики [math]G[/math] и введем продукцию [math]\$ \rightarrow \epsilon[/math]; остальные продукции [math]G[/math] и [math]G`[/math] одинаковы. Поскольку [math]L(G`) = L`[/math], получаем, что [math]L(G) = L[/math]. Утверждаем, что [math]G[/math] однозначна. Действительно, левые порождения в [math]G[/math] совпадают с левыми порождениями в [math]G`[/math], за исключением последнего шага в [math]G[/math] — изменения [math]\$[/math] на [math]\epsilon[/math]. Таким образом, если бы терминальная цепочка [math]w[/math] имела два левых порождения в [math]G[/math], то [math]w\$[/math] имела бы два порождения в [math]G`[/math]. Поскольку [math]G`[/math] однозначна, [math]G[/math] также однозначна.

[math]\triangleleft[/math]