Пәнін оқыту-әдістемелік кешен 5В060200 «Информатика» мамандығына арналған ОҚУ-Әдістемелік материалдар



жүктеу 2,68 Mb.
бет108/127
Дата19.11.2018
өлшемі2,68 Mb.
#20473
1   ...   104   105   106   107   108   109   110   111   ...   127

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

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

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



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

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

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

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

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

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



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

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

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



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

Қадам 3.Егер Ni ≠Ni1,онда 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 жиынның бірізділік жақындауын құрамыз :

N0=Ø;

N1= {A,B};

N2={S,A,B};

N3={S,A,B}.

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

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

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



{X | X VN,^3(X => *x), xV*T}

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



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

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



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

жүктеу 2,68 Mb.

Достарыңызбен бөлісу:
1   ...   104   105   106   107   108   109   110   111   ...   127




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау