Алгоритм 4.2.Терминал еместі шектету

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

Шығу: КС-грамматикасы G^′ = (VT, VN′, P^′, S), L(G^′) = L(G) және барлық Z VN′ үшін қорытындылар бар Z => *x, мұнда xgVj .

Қадам 1. Терминал емес жиынды алгоритм4.1. көмегімен анықтау.

Қадам 2. V_N′ =V_N∩N,, N_Б = V_N − V_N′, P^′ = P − P_Б есептеу, мұндағы P_Б P –бұл жиын ережесі. Ол керексіз терминал емес X NБ құрайды..

Мысал 4.2. G = ({a, b, c}, {S, A, B, C},P, S грамматикасы берілген ережелермен Р: 1)S→ab; 2)S → АС; 3)А→АВ; 4)B→b; 5)С→сb. Оны эквивалентті грамматикаға G^′ алгоритм 4.2 бойынша келтіреміз:

N₀ = Ø;

N₁={S,B,C}.

N₂={S,B,C}.

N₁ = N₂, онда N ={S,B,C}. Терминал емес керексіздерді өшіргеннен кейін және қорытынды ережесіннен кейін G^′=({a,b,c},{S,B,C},P^′,S) грамматикасын ережелерімен аламыз, P^′: 1) S → ab; 2)B→b; 5)C→cb.