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

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

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

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

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

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

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

Мысал 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}.

Қадам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.

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

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

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

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

1) L → M ; 2 ) M → N; 3) N —→ N+ | n. Эквивалентті грамматиканы G алгоритм 4.5 бойынша құрамыз.

Қадам 1.;N₀^L={L}

N₀^L = {L};

N₁^L = {L, M};

N₂^L = {L, M, N};

N₃^L = {L, M, N}.

Сонымен қатар N₂^L = N₃^L , то N ^L = {L, M, N}.

Сонымен қатар N₁^M = N₂^M , то N^M = {M, N}.

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

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

Қадам 1. Записать все правила для нетерминала X терминал емес барлық ережелерді жазу, біркелкі префиксы α V* барларды альтернативті түрдегі: X →αβ1 αβ 2 K αβ n β1 β 2 K β n V

Қадам 2. Сол жақтағы жақшадан префикс α- ны альтернативтің әрбір жолына шығару:.X → α (β1 | β2 | K | β n Рп )•

Қадам 3. Терминал еместі Y жаңа белгімен белгілеймі қалған жақшадағы: X →αY, Y → β1 | β 2 |K| β n.

Қадам 4. Терминал еместі жаңа териналь емес Y –мен толықтырамыз және ережені X және Y өзгертеміз.

Қадам 5.Қадам 1-4 қайталаймыз.

Эквивалентті грамма­тиканы G^′ алгоритму 4.6 құрамыз:

Қадам1. S→kSl|kSm|n.

Қадам2. S→kS(l|m)|n.

Қадам 3,4. Терминал еместі жаңа териналь емес С –мен толықтырамыз, сонда G^′ = ({k,l,m,n}, {S, C},P^′, S) грамматикасын ережесімен аламыз ^P: 1) S → kSC; 2)S→n; 3) C → m.

Алгоритм 4.7. Тура сол рекурсияны шектеу.

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

Шығу: Эквивалентті КС-грамматикасы G'= (VT,VN′,P^′,S′ ереже түрінсіз. A→Aα, A V_N, α V _*

Қадам 1. Грамматикадан барлық X терминал емес рекурсия ережелерін шығарамыз:

Қадам 3. X оң бөлік үшін рекурсивті ережені ауыстырамыз, жаңа терминал еместі қолдана отырып, бірақта тіл өзгермеуі қажет:

Қадам 4. Жиынды жаңа терминал емес Y грамматикасымен толықтырамыз. Қадам3–тегі алынған жиынның грамматика ережесімен толықтырамыз

1. 
   КС-грамматиканың келтірілген түрі қалай аталыды?
   
2. 
   КС-грамматиканың келтірілген алгоритмын көрсетіңіз.