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

жүктеу 308,64 Kb.

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

1 2 3 4 5

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

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

Қажетті құрал-жабдықтар: дербес компьютер, программалар жүйесі.

Зертханалық жұмысты орындауға арналған әдістемелік нұсқау:

Контексті-тәуелсіз (КТ) грамматика

Мазмұны: КТ-грамматиканың бірмәнділігі. Оң жақ және сол жақ шығару. Контексті-тәуелсіз грамматикаларды келтіру және түрлендіру эквиваленттілігі.

Мақсаты: «эквивалентті грамматика», «КС-грамматикасы» түсініктерін қалыптастыру;- Эквивалентті контекстті-бос грамматикканы қолдану.

Негізгі теория

Анықтама 4.1. КС-грамматикасы келтірілген болады, егер оларда цикл болмаған жағдайда. Егер оларда циклдар болмаса, ε-ережесі және керексіз символдар болса.

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

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

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

Шығу: Грамматика тілінің бар екенін немесе жоқ екенінін қорытындысы.

Жиынның терминалды емес екенін терминалды жолдардан анықтаймыз, N = {Z | Z V_N, Z => *x, x VT*.

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

Қ адам 2. есептейміз.

Қадам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. Керексіз символдар грамматикасы деп:

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

{X | X V_N,^3(X => *x), x V^*_T}

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

{X | X V_N, -3(S => *αXβ), 3(Х => *x); α, β V*; x V^*_Т);

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

{X | X V_T,^3(S => *αXβ); α, β V*}.

жүктеу 308,64 Kb.

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

1 2 3 4 5