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

жүктеу 14,81 Mb.

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

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

Мысал 5.1. КС-грамматикасы берілген:

G({+, (, ), a}, {S, A}, {S→S+A | A, A→(S) | a}, {S}). МП-автоматының құру жүйелілігі мынадай түрде болады.

1) Q= {q},q0 = q, T= {+,(,), a },N= {+,(,), a, S,A},N0 = S, Z=Ø.

2) F(q, ε, S) = (q, S+A), F(q, ε, S) = (q, A), F(q, ε, A) = (q, (S));

F(q, ε,A) = (q,a).

3) F(q, t, t) = (q, ε ) әрбіреуі үшін t {+, (, ), a}.

МП-автоматы бойынша құрылған (а) жолын тану 5.1 кестесінде көрестілген. Алынған МП-автомат терминалсыз болады.

Кесте 5.1 – МП-автоматы бойынша (а)жолын анықтау

Конфигурации номері	Ағымдағы қалпы	Енгізу жолы	Магазин құрамы
1	Я	(a)	S
2	я	(a)	А
3	Я	(a)	(S)
4	я	a)	S)
5	Я	a)	A)
6	Я	a)	a)
7	Я	)	)
8	Я	£	£

Алгоритм 5.3. КС-грамматика бойынша кеңейтілген МП-автоматын құру

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

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

Шығару: кеңейтілген МП-автомат M = (Q, T, N, F, q0,N0, Z) сонда, ол

L(M) = L(G).

1 Қадам. Қою Q = {q, r}, q₀ = q, Z = {r},N= V_T V_N {#}, T = V_T,

2 Қадам. Әрбір ереже үшін (A → β) P, где β V* , магазин функциясын құру F(q, ε, β) = (q, A) енгізу жолының ағымдағы символына қарамастан, ереженің оң жағын жоғарыдағы стекта терминалсызындағы сол жағымен ауыстыру.

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

Қадам 4. Автоматты соңғы қалпына аудару үшін магазиндік функцияны қарастыру F(q, ε,#S) = (r, ε).

жүктеу 14,81 Mb.

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

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