«Соңғы автоматтар және формальдік тілдер теориясы»

жүктеу 14,81 Mb.

бет	116/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 ... 112 113 114 115 116 117 118 119 ... 127

Анықтама 5.4.
Анықтама 5.5.
Алгоритм 5.2. МП-автомат тын КС-грамматик а бойынша құрылымы

Анықтама 5.3. МП-автоматы ω енгізу жолын рұқсат етеді, егер конфигурациялар бойынша жол бар болса (q0,ω,N0)|=*(q,ε,α)кейбіреулер үшін q Z және

αN*.

Анықтама 5.4. МП-автоматымен анықталған L, тілі М көптік түрде анықталады:

L(M) = {ω | ω T * және )(q0,ω,N0)|=*(q, ε,α кейбіреулер үшін q Z және αN*}.

Анықтама 5.5. МП-автоматы магазин функциясымен

F : (Q× (T

{ε }) × N*) → P(Q× N*)

кеңейтілген МП-автоматом деп аталады, бұл дегеніміз стектың басында соңғы ұзындығындағы тізбекті өзгерте алатын автомат.

Сол бұрынғы тілді анықтайтын КС-тілдер, МП-автоматтар және кеңейтілген МП-автоматтар болады.
Алгоритм 5.2. МП-автоматтын КС-грамматика бойынша құрылымы

Сол жақ талдауын жүргізетін МП-автоматын құрайық. Берілген автоматтың тек бір ғана қалпы болады және ол магазинді босатып енгізу жолын қабылдайды. Ағымдағы сентенцияны орналастыру үшін стек қолданылады, бастапқыда ол грамматиканың бас символы болады. Келесі сентенция жоғарғы стектың анықталмағандығы болып табылады.

Енгізу: КС-грамматика ) G = (VT, VN ,P,S).

Шығару: МП-автоматы М = (Q, T, N, F, q0,n0, Z сондай, бұл дегеніміз L(M) = L(G).

1 қадам.Қою Q = {q}, q₀ = q,Z=∅,N=V_T

V_N, T= V_T, N₀= S.

2 қадам. Әрбір ереже үшін (А→β) P, где ,β V _*

магазиндік функцияны құру F(q, ε, A) = (q, β). Грамматика ережесі бойынша стектың басында бұл функциялар терминалсыздың орнын басуға бұйрық береді.

3 қадам. Әрбір t VT үшін магазиндік функция құру

F(q, t, t) = (q, ε), ол стектан символды шығарады, ол енгізумен сәйкес келеді, және ол оқитын басты жылжытады. Бұл функциялар стекты босатуды қамтамасыз етеді.

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 ... 112 113 114 115 116 117 118 119 ... 127