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

- Эквивалентті контекстті-бос грамматикканы қолдану.

КС-грамматикасына негізгі алгоритмдерді қарастырамыз.

Алдымен басқа зерттеулермен және КС-грамматикасы грамматика тілінің тексерілуін орындайды.

Алгоритм 4.1. Грамматика тілінің бар екенін тексеру.

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

=> *x, x

Қадам 1. N0=Ø қоямыз.

Қадам 3.Егер Ni ≠Ni₋1,онда i=i+1,2- пункке өтеміз.Әйтпесе N = Ni деп санайды.

Егер S N, онда грамматика тілі бар деген хабарлама шығады, әйтпесе хабарлама жалған болып шығады.

Мысал 4.1. G=({0,1}, {S, A, B},P, S),грамматикасы берілген, ондағы жиын Р: \)S→AB\ 2)A→0A; 3)A →0; 4)B →1. N жиынның бірізділік жақындауын құрамыз :

N₀=Ø;

N₁= {A,B};

N₂={S,A,B};

N₃={S,A,B}.

N₂=N3, әйтпесе N= {S, A, B}, одан язык грамматика тілін бар екенін көз жеткіземіз.

Анықтама 4.2. Керексіз символдар грамматикасы деп:

а) терминал емес, терминальды жолдардардан туындамауы. Жиын символдар

xV

б) терминал еместің жетіспеуі , терминальды жолдардың туындауы жиынның символы

V*;

x

в) терминалдың жетіспеуі , жиынның символы