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

Алгоритм 4.2.Терминал еместі шектету

жүктеу 14,81 Mb.

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

1 ... 105 106 107 108 109 110 111 112 ... 127

Мысал 4.2.
Алгоритм 4.3. Жеткіліксіз символдарды шектеу.

Алгоритм 4.2.Терминал еместі шектету.

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

Шығу: КС-грамматикасы G^′ = (VT, VN′, P^′, S), L(G^′) = L(G) және барлық

Z

VN′ үшін қорытындылар бар Z => *x, мұнда xgVj .

Қадам 1. Терминал емес жиынды алгоритм4.1. көмегімен анықтау.

Қадам 2. V_N′ =V_N∩N,, N_Б = V_N − V_N′, P^′ = P − P_Бесептеу, мұндағы P_БP –бұл жиын ережесі.Ол керексіз терминал емес X

NБ құрайды..

Мысал4.2. G = ({a, b, c}, {S, A, B, C},P, S грамматикасы берілген ережелермен Р: 1) S→ab; 2)S → АС; 3)А→АВ; 4)B→b; 5)С→сb.

Оны эквивалентті грамматикаға G^′ алгоритм 4.2 бойынша келтіреміз:

N₀ = Ø;

N₁={S,B,C}.

N₂={S,B,C}.
N₁ = N₂, онда N = {S, B, C}. Терминал емес керексіздерді өшіргеннен кейін және қорытынды ережесіннен кейін G^′=({a,b,c},{S,B,C},P^′,S) грамматикасын ережелерімен аламыз, P^′: 1) S → ab; 2)B→b; 5)C→cb.

Алгоритм 4.3. Жеткіліксіз символдарды шектеу.

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

Шығу: КС-грамматикасы G' = {Vj, VN′, P^′, S, ол L{G') = L(G және барлық Z

V′ қорытындысы бар S => *αZβ, мұндағы α, β

(V′)* .

Z грамматики G грамматикасының Z символының жиының анықтаймыз. Жиын

W = {Z | Z

V, 3 (S => *αZβ); α, β V*}.

Қадам1. W₀= S қоямыз.

адам 2.Келесі жақындауды төмендегі үлгідей есептейміз:

Қадам3. Егер Wf ≠ W_i-1онда i:=i+1 2-ші қадамға өтеміз, әйтпесе W = Wi есептейді.

Қадам 4. V'_N =V_N ∩W,VT′ =V_T ∩W,V_Б V−W,P^′=P −P_Б ,есептеу,мұндағы PБ P - Бұл жиын ережесі. Ол жеткіліксіз символдарды құрайды.

жүктеу 14,81 Mb.

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

1 ... 105 106 107 108 109 110 111 112 ... 127