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

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).

α

n V

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

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

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

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

Мысал 4.6. G = ({k,l,m,n},{S},P,S) грамматикасы ережелерімен P: 1) S → kSl; 2) S → kSm; 3) S → n.

Эквивалентті грамма­тиканы 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).

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

Қадам 5. Барлық рекурсивті терминал емес грамматикаға қадам1-4 қайталаймыз.Одан кейін терминал емес жиынды және ережені мына түрде қарастырамыз VN′ және .^P_′
№ 4 зертханалық жұмысқа орындау тапсырмалары.