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

жүктеу 14,81 Mb.

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

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

Алгоритм 4.4. ε - ережесін шектету

Мысал 4.3. G = ({a, b, c}, {S, B, C},P, S ережесімен жиын берілген. )S→ab; 2)B→b; 5)C→c_bОны эквивалентті етіп, G^′ грамматикасын алгоритму 4.3 бойынша орындаймыз:W₂={S,a,b}.

W1=W2, онда W={S, a, b}. Жеткіліксіз символдардың жиыны = {B, C, c}. Одан кейін жеткіліксіз символдарды өшіргеннен соң

G^′ = ({a, b}, {S}, P, S) грамматикасын P^′: . S → ab ережесін аламыз.

Алгоритм 4.4. ε-ережесін шектету

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

Шығу: Эквивалентті КС-грамматикасы G^′ = (VT, VN′, P^′, S^′) ε- ережесіз терминаль емес символдардың барлығы үшін, тек ғана бастапқыға емес, ол оң бөліктегі грамматика ережелерімен кездеспеуі ерек.

Қадам 1. G шығару грамматикасында найти ε терминаль емес минальды символдарды A VN, A =>*£ табу керек.

}N₀ = {A | (A → ε) P қоямыз.
N_t = N_i−1 {B|(B →α)P,α Ni*− 1 есептейміз.
Егер Ni ≠Ni₋1, i:=i+ I 1.2пункке өтеді әйтпесе N = Ni есептейді.

Қадам 2. G грамматикасын жиыннан Р ауыстырамыз P.

Қадам 3. P^′жиынын ережелермен толықтырамыз , олар бұл жиынның әрбір ережесін шығару жолымен терминаль емес оң бөлігінде шығады..

Қадам 4. Егер SN, онда P^′= P{S^′ →ε,S^′ → S},VN′ =V_N S^′, Мұндағы V ∩ {S^′} = ∅; әйтпесе V_N′ =V_N, S^′ = S.

жүктеу 14,81 Mb.

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

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