Сабақтың мақсаты Оң жақты және сол жақты шығару түсінігі. «Грамматиканың эквиваленттілігі», «келтірілген кс-грамматика»

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

жүктеу 308,64 Kb.

бет	4/5
Дата	03.02.2022
өлшемі	308,64 Kb.
	#35461
түрі	Сабақ

1 2 3 4 5

4 зертханалық жұмыс (1)

Алгоритм 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 - Бұл жиын ережесі. Ол жеткіліксіз символдарды құрайды.

Мысал 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 ережесін аламыз.

жүктеу 308,64 Kb.

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

1 2 3 4 5