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



жүктеу 2,68 Mb.
бет102/127
Дата19.11.2018
өлшемі2,68 Mb.
#20473
1   ...   98   99   100   101   102   103   104   105   ...   127

Зертханалық жұмыс № 2
Шекті айқындауыштар, берілген автоматты грамматика үшін шекті автоматтың ауысу графын құру және өңдеу
Мазмұны: Шекті айқындауыштардың эквиваленттілігі және бір мәнділігін құру, тұрақты грамматика бойынша шекті автоматтарды құру, «детерминатты емес және детерминантты емес шекті автоматтар» ұғымын бекіту

Мақсаты: - «жүйелік грамматика», «детерминалды емес және детерминалды соңғы автомат» шек қою;

- жүйелік грамматикада соңғы автоматты форматтау және и преобразования детерминалды соңғы автомата детерминалды соңғы автоматқа ауыстыру.

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

Жүйелі грамматиканы тану үшін соңғы автомат қажет (СА).



Анықтама 2.1. Детерминалды соңғы автомат (ДСА) деп бестік объекті айтамыз.

M=(Q,T,F,H,Z), (2.1)



Q- болған жағдайда - соңғы жиын автомат жағдайы;

Т - соңғы жиын кіру автоматы;

F – ауысу функциясы, Q × T жиынын көрсететін Q жиынында;

Н - автомат жағдайындағы бастапқы соңғы жиын;

Z - автомат жағдайындағы қорытынды жиыны, Z Q.

Анықтама 2.2. детерминалды емес соңғы автомат (ДСА) деп соңғы автоматты айтады, ауысу функциясында қолданылатын өту функциясы Q ×Т ішкі жиын автоматындағы жиындар)P(Q), ағымдағы қос жэиындар секілді өту функциясы біркелкі емес, (q, t ) автомат жиынына ұқсас q P(Q).
Өту функцияларын көрсету тәсілдері

Командалық тәсіл. СА – та әрбір команда пішін түрінде былай жазылады F(,q, t) = p болғанда



q,.pQ,tT

Кестелік тәсіл. кесте жолдарының ауысуы кіру символ автоматына ұқсас t T, а бағандар – Q жағдайында. Кесте ұяшықтары жаңа жағдайлармен толтырылады, функция мағынасына ұқсас)F(q,t.

Анықталмаған өту функциялары бос ұяшық кестелерге ұқсас.



Графикалық тәсіл. автоматта диаграмма құрылады – ол ретсіз таңбаланған граф болып табылады. Граф төбелері аттармен таңбаланған . Доға qжағдайыннан p жағдайынаапарады және барлық t T символдарына таңбаланады, для которых F(.q, t) = p Төбесі, кіру автоматына ұқсас және бағыттауышпен жабдықталады. Граф қорытындысы екі концентрлі шеңберлермен белгіленеді.

Алгоритм 2.1. Жүйелік грамматикада СА құру



Кіру: жүйелік грамматика G = (VT ,VN,P,S).

Шығу : КА M = (Q, T, F, H, Z).

Қадам 1. Грамматиканы ереже бойынша толтырамыз А A → aN, A VN,a VT және N болғанда - жаңа нетерминал, әрбір ереже үшін А A → a, егер грамматикада оған ұқсас ереже болмаса A→aB, В B ∈VN болғанда.

Қадам 2. Бастапқы символ грамматикасы S СА бастапқы H жағдайына берілген.. Терминалды еместен жиын автоматын анықтауға болады Q = VN {N}, ал терминалдардан - кіру алфавитіндегі жиын символы T = VT.

Қадам 3. Әрбір ереже бойынша A→aB өту функциясын анықтау F(,A,a) = B болғанда A,.BVN,a VT

Қадам 4. Қорытынды жағдайда барлық шыңдарды қосу керек, символдармен таңбаланған В BVN ереже түрінен A→aB, олар үшін қолданылатын ұқсас ережелер А A → a, A болғанда ,.B VN,a VT

Қадам 5. Егер грамматикада S→ ε ережесі орындалса, онда S –бастапқы символ грамматикасы болып табылады, әлде S – ті қорытынды жиынға жіберу. Адым 6.НСА алынса, онда оны ДСА деп аламыз.

Алгоритм 2.2. НКА – ны ДКА-ға өзгерту

Кіру: НКА М = (Q, T, F, H, Z).

Шығу: ДКА М' = (Q, T, F, H, Z′).

Қадам 1. M ДКА кестесіндегі бірінші бағанды ауыстыру (бастапқы жиын жағдайы) НКА M .



Қадам 2. Mөту кестесіндегі бағанды толтырамыз, D символымен таңбаланған, ол үшін әрбір жолдардағы D символына қол жеткізу керек x кіру символдары кезінде. Әрбір табылған R жиынды D бағанына M кестесіне сыйдыру керек. (сонымен қатар ∅).

F(D,x) = {s|s F(t,x) t ∈D} үшін.

Қадам 3. Әрбір R жиыны үшін (∅ басқасы), D бағанында Mөту кестесінде алынған, кестеге жаңа бағандарды құру, R – мен таңбаланған.



Қадам 4. Егер СА M өту кестесінде толтырылмаған баған болса, онда 2 адымға шығуға болады.

Қадам 5. Z ДКА Mжиынында әрбір жиынды қосу керек, M өту кестесіндегі бағандарымен таңбаланған және q Z НКА Mұсталынған .

Қадам 6. Кестеге жаңа жиындарды құрып, ДКА M анықтау. таблицу



жүктеу 2,68 Mb.

Достарыңызбен бөлісу:
1   ...   98   99   100   101   102   103   104   105   ...   127




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

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