Зертханалық жұмыс № 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′ анықтау. таблицу
Достарыңызбен бөлісу: |