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

жүктеу 14,81 Mb.

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

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

Алгоритм 4.5. Тізбек ережесінің шектелуі.

Мысал 4.4. G = ({0,1}, {S, A, B},P, S грамматикасы Р ережелерімен берілген: 1)S→A B; 2)A→0A|ε; 3)B → 1 B | ε.Оны эквивалентті грамматикаға алгоритму 4.4. бойынша келтіреміз.

N1 = N2, жиын құрылған және N= {S,A,B}.

Қадам 2, 3. P^′жиыны : 1) S→AB|A | B; 2) 0A→0A|; 3).B→1B|₁

Қадам4. S N ,то терминал емес С енгіземіз және P жиынын C →S|ε толықтырамыз^′..Грамматика мұндай түрге енеді:: G^′ = ({0,1},{S,A,B,C},P,C) ережелерімен:^P ′ ; 1) C → S |ε ; 2) S → AB | A| B; 3) A → 0A| 0; 4) B →1B |1.

Алгоритм 4.5. Тізбек ережесінің шектелуі.

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

Шығу: Эквивалентті КС-грамматикасы G^′= (VT,VN′,P^′,S^′) тізбек ережесіз, ереже түрі A→B, мұндағы A,.BV_N

Қадам 1. Для каждого нетерминала A терминал емес үшін жиынды есептейміз ,N = {B | A => *_B мұндағы В е V^N.

Nq = {A қоямыз.
Nf = NiA−1 {C|(B →C)P,B NiA−1, CV_n есептейміз
Егер Ni ^A≠N^A_i₋₁, онда i:=i+1 1.2.пунктіне көшеді, әйтпесе N A=Ni _A

Қадам 2. P^′ жиынын құрамыз: егер (B→α)

P тізбектік ереже болмаса (aeVft),онда P^′ ережесі A→ α әрбір A үшін.

жүктеу 14,81 Mb.

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

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