Въведение в анализа
Теория на опашката (QS)
Алгоритъм за конструиране на CF-граматика от MP-автомат
Нека първо да дадем неформална мотивация за конструкцията, която ще бъде дадена по-долу. Ще разгледаме MP-автомата като "играч", който задава цели от следната форма: "да бъдеш в състояние [math]q[/math] и да имаш най-горния символ на магазина [math]Z[/math] , отиде в състоянието [math]s[/math] ". Съгласни сме да напишем такава цел като тройна [math][qZs][/math] . Как нашият "играч" може да постигне целта? Ако наборът от команди на автомата ("правилата на играта") съдържа командата
където за всеки [math]i[/math] имаме [math]X_i[/math] — символът за натискане [math](X_i\in \Gamma)[/math] , тогава след изпълнение на тази команда MP-автоматът ще премине в състояние [math]r[/math] .
Ако [math]r=s[/math] , тогава целта е постигната, в противен случай поставяме целта [math][rX_1s_1][/math] , и след като я достигнем, поставяме целта [math][s_1X_2s_2][/math] и т.н. След като достигне целта [math][s_X_ks][/math] , "играчът" също достига целта [math][qZs][/math] . Тъй като се взема предвид толерансът с празен магазин, символите [math]X_i[/math] трябва да напуснат магазина на свой ред и само в този случай може да бъде постигната "глобалната" цел на MP-автомата: [math][q_0Zq_f],
q_f\in F[/math] ("като сте в първоначалното състояние и имате началния символ на списанието като горен символ на списанието, влезте в едно от крайните състояния, изпразвайки списанието"). Тъй като, най-общо казано, "играчът" не знае предварителнопоследователности от състояния [math]s_1,s_2,\ldots,s_[/math], водещи до целта, трябва да премине през всички такива последователности.
Тези неофициални съображения са в основата на следната конструкция.
Нека е даден MP автомат [math]M=(Q,V,\Gamma,q_0,F,Z_0,\delta)[/math]. Ние дефинираме CF-граматика [math]G_M=(V,N,S,P)[/math], чиято терминална азбука съвпада с входната азбука на MP-автомат [math]M[/math], както следва.
Нетерминалната азбука [math]N[/math] на граматика е набор, който е в едно-към-едно съответствие с набора от всички подредени тройки от формата [math](q,Z,s)[/math] , където [math]q,s\in Q,
Z\in\Gamma[/math] , допълнен със символа [math]S[/math] , който не принадлежи към нито едно от множествата [math]Q,V,\Gamma[/math] и е обявен за аксиома на граматиката. Подредените тройки от този вид обикновено се записват като [math][qZs][/math] , интуитивно разбирайки всяка такава тройка като целта, описана по-горе.
Наборът от правила за извод [math]P[/math] на граматиката [math]G_M[/math] е конструиран, както следва:
a) ако командата е [math]qaZ\to rX_1X_2\ldots X_k,
k\geqslant1[/math] принадлежи към командната система [math]\delta[/math], тогава [math]P[/math] съдържа всички правила на формата
за всяка последователност [math]k[/math] от състояния [math]s_1,\ldots,s_k[/math] на набора [math]Q[/math] (по този начин [math]Q^k[/math] от правила за всяка команда от посочения тип се добавя към [math]P[/math]);
Пример 8.17. За MP-автомат [math]M=(\, \, \, q_0, \, Z,\delta)[/math] с набор от команди [math]\delta[/math] , имащ формата
ще конструираме еквивалентна CS-граматика. Може да се докаже, че този MP-автомат допуска езика [math]\[/math] . Имайте предвид, че MP автоматът [math]M[/math] допуска празна верига чрез прилагане към началнияконфигурация [math](q_0,\lambda,Z)[/math] последна команда. Граматиката, конструирана съгласно тази система от команди, ще има следната форма:
s_1,s_2\in \,\\ &[q_1as_2]\към a[q_1as_1][s_1as_2],
s_1,s_2\in\,\\ &[q_1aq_2]\to b,\qquad [q_2aq_2]\to b,\\ &[q_2Zq_0]\to\lambda,\qquad [q_0Zq_0]\to\lambda. \край[/math]
Подчертаваме, че във втория и третия ред има не едно, а всяко [math]3^2=9[/math] правила (броят на всички последователности от две състояния от триелементния набор от състояния). Нека изведем в тази граматика веригата [math]aabb:[/math]
Във втората стъпка от този извод ние прилагаме правилото за извод на деветте правила от втория ред, което се получава чрез заместване на състоянието [math]q_2[/math] вместо [math]s_1[/math] и вместо [math]s_2[/math] състоянието [math]q_0[/math] . Ние „отгатваме“ тези състояния, знаейки (от командната система на оригиналния MP-автомат), че нашият MP-автомат може да достигне крайното състояние след прочитане на (непразния) входен низ само от състоянието [math]q_2[/math] . В същото време, ако използвахме правилото за втори ред във втората стъпка, което се получава чрез заместване на [math]s_1=q_1,
s_2=q_2[/math], ще има безполезен нетерминал [math][q_1aq_1][/math] и изходът ни ще бъде блокиран.
По подобен начин в третата стъпка се използва правилото на деветте правила на третия ред, в което [math]s_1=s_2=q_2[/math] . След това прилагаме правилата на четвъртия, петия и шестия ред на свой ред, завършвайки изхода.
Ако сега „преброим“ на стъпки символите push-pull, затворени в квадратни скоби между състоянията в конструирания изход, тогава получаваме [math]Z,aZ,aaZ,aZ,Z[/math] , т.е. получите промяна в съдържанието на магазина (без да броим последната стъпка, когато тя приключи
опустошение на лен),представени в следния изход на набор от конфигурации на MP-автомат [math]M\colon[/math]
Това извеждане не е нищо друго освен разрешаване на последователност от конфигурации за веригата [math]aabb[/math] . Четейки последователностите от състояния в квадратни скоби, ще стигнем до последователността от състояния, през които преминава MP автоматът, позволявайки веригата, написана по-горе.
Наистина, след първата стъпка на извод в граматиката, получаваме последователността [math]q_0,q_0[/math] , която може да се тълкува по следния начин: „преход (връщане) от състоянието [math]q_0[/math] към същото състояние [math]q_0[/math] след прочитане на входната верига“.
След втората стъпка ще имаме [math]q_0,q_1,q_1,q_2,q_2,q_0[/math] , което означава: „за да се върнете към [math]q_0[/math] , първо трябва да стигнете до [math]q_2[/math] чрез [math]q_1[/math] “).
След третата стъпка получаваме g [math]q_0,q_1,q_2,q_0[/math] . Това е получената последователност от състояния, тъй като всички следващи стъпки на MP-автомата са свързани с "изтласкване" на символи от магазина и не водят до появата на нови цели.
Като правило, граматиката, която е конструирана по горния начин според MP-автомата, се оказва много тромава, съдържа много безполезни и непостижими символи. Това се дължи на факта, че съдържа произволни последователности от състояния на MP автомат с фиксирана дължина. По отношение на пример 8.17 е лесно да се напише граматиката за езика [math]\[/math] директно в този случай:
От тази граматика може да се конструира MP-автомат, като се използва алгоритъмът от първата част на доказателството на основната теорема, който е много по-прост от оригиналния. Командната му система ще изглежда така:
В общия случай проблемът за признаване на еквивалентността на двама МПавтомати (за разлика от същия проблем за крайни автомати) не е разрешим и няма общ алгоритъм за "опростяване" (в известен смисъл, "минимизиране") на MP автомат, въпреки че, както току-що видяхме, това е напълно възможно в конкретни случаи.
Теорема 8.7. MP-автоматът [math]M[/math] е еквивалентен на граматиката [math]G_M[/math] .
Чрез индукция върху дължината на [math]n[/math] производната в [math]M[/math] доказваме, че [math]Z\in\Gamma,
(q,x,Z)\vdash^n(r,\lambda,\lambda)[/math] за всеки [math]q,r\in Q,
x\in V^[/math] дава [math][qZr]\vdash^x[/math] в [math]G_M[/math] .
Ако [math]n=1[/math] , т.е. [math](q,x,Z)\vdash(r,\lambda,\lambda)[/math] , тогава [math]x\in V\cup\[/math] и [math]\delta[/math] има командата [math]qZx\to r\lambda[/math] , откъдето [math]P[/math ] има правилото [math][qZr]\to x [/math] и [math][qZr]\vdash^x[/math] .
Нека това, което се доказва, е вярно за всеки [math]n\leqslant m-1[/math] , където 1">[math]m>1[/math] , и нека [math](q,x,Z)\vdash^m(r,\lambda,\lambda)[/math] , където първата стъпка от съответното извеждане е
Подобно на доказателството на теорема 8.6, доказваме, че тогава има вериги [math]x_1x_2\ldots x_k[/math] и последователност от състояния [math]s_1,\ldots,s_[/math], така че [math]y=x_1x_2\ldots x_k[/math] и
където за всяко [math]i=\overline[/math] това е [math]0\leqslant m_i\leqslant m-1[/math] . Следователно, по силата на теорема 8.5, за всеки [math]i=\overline[/math] имаме
където [math]s_0=p[/math] и [math]s_k=r[/math] и чрез индукционната хипотеза [math][s_X_is_i]\vdash^x_i[/math] .
Следователно, според конструкцията на граматиката [math]G_M[/math] има възможност за извеждане (което трябваше да бъде доказано)
Нека веригата [math]x[/math] е разрешена от MP-автомат [math]M[/math] . Тогава [math](q_0,x,Z)\vdash_^(q_f,\lambda,\lambda)[/math] , където [math]q_f\in F[/math] е едно от крайните състояния на MP автомата [math]M[/math] . Според току-що доказаното, в този случай за граматиката [math]G_M[/math] имаме [math][q_0Z_0q_f] \vdash_^x[/math] . Но тъй като наборът от правила за граматически изводи [math]G_M[/math] съдържа правилото [math]S\to[q_0Z_0q_f][/math] , получаваме [math]S\vdash_ [q_0Z_0q_f]\vdash_^x[/math] , т.е. [math]x\in L(G_M)[/math] . И така [math]L(M)\subseteq L(G_M)[/math] .
За да докажем обратното включване, първо доказваме, че [math][qZr]\vdash_^x[/math] предполага [math](q,x,Z)\vdash_^(r,\lambda,\lambda)[/math] за всяко [math]q,r\in Q,
x\in V^[/math] и [math]Z\in\Gamma[/math] . Нека направим индукцията отново върху дължината на изхода (в граматиката [math]G_M[/math]). С [math][qZr]\vdash x[/math] получаваме правилото [math][qZr]\to x[/math] в [math]P[/math] и, следователно, командата [math]qxZ\to r\lambda[/math] в [math]\delta[/math] , т.е. [math](q,x,Z)\vdash (r,\lambda,\ ламбда)[/math] . Ако [math][qZr]\vdash^mx[/math] за някои [math]m\geqslant1[/math], тогава [math]x=ay[/math] за някои [math]a\in V\cup\[/math] и
и за всички [math]i=\overline[/math] имаме [math][s_X_is_i]\vdash^x_i[/math], където [math]s_0=p,
s_k=r[/math] и [math]1\leqslant m_i\leqslant m-1[/math], така че [math]y=x_1x_2\ldots x_k[/math] .
По индукционната хипотеза тогава за всеки такъв [math]i[/math] имаме
Но тъй като първата стъпка на извод в граматиката, посочена по-горе, е възможна само ако има команда в MP-automaton [math]qaZ\to pX_1X_2\ldots X_k[/math] , тогава
Ако сега веригата [math]x[/math] се генерира от граматиката [math]G[/math], т.е. [math]S_^x[/math], тогавапървата стъпка за извличане на [math]x[/math] от [math]S[/math], според дефиницията на [math]G_M[/math] системата от граматични правила, ще бъде [math]S\vdash [q_0Z_0q_f][/math] за някои [math]q_f\in F[/math] и следователно [math][q_0Z_0q_f] \vdash_ ^x[/math] . След това, чрез току-що доказания [math](q_0,x,Z_0) \vdash_^ (q_f,\lambda,\lambda)[/math] , тоест [math]x\in L(M)[/math] . И така, [math]L(G_M)\subseteq L(M)[/math] и тъй като обратното включване вече е доказано, тогава [math]L(M)=L(G_M)[/math] .
От доказаните теореми 8.6 и 8.7 получаваме следната теорема.
Теорема 8.8. Един език е контекстно-свободен тогава и само ако е разрешен от някой MPF.
Забележка 8.10. Има една полезна модификация на конструкцията на MP-автомат от CF-граматика. Да се върнем към пример 8.16. Може да забележите, че в този пример дясната страна на всяко граматично правило започва с някакъв терминал. Вземането под внимание на тази характеристика ни позволява да намерим друг MP-автомат, който, както е лесно да се покаже, също е еквивалентен на дадената граматика. Командната система на този автомат има следния вид:
Като цяло, ако дясната страна на което и да е граматично правило е [math]a\xi[/math] , където [math]a\in V[/math] , MP-автоматът, еквивалентен на дадената граматика, се определя от команди от формата
(първият е за правилото [math]A\to a\xi[/math] ). В тази модификация MP автоматът записва в магазина "опашката" на дясната страна на правилото след първия терминал.
Може да се докаже, че всяка CF-граматика може да бъде дефинирана с правила от този вид (така наречената нормална форма на Грайбах).
|