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

жүктеу 14,81 Mb.

бет	102/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

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 V_N,a VT және N болғанда - жаңа нетерминал, әрбір ереже үшін А A → a, егер грамматикада оған ұқсас ереже болмаса A→aB, В B ∈VN болғанда.

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

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

Қадам 4. Қорытынды жағдайда барлық шыңдарды қосу керек, символдармен таңбаланған В BVN ереже түрінен A→aB, олар үшін қолданылатын ұқсас ережелер А A → a, A болғанда ,.B V_N,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^′ анықтау. таблицу

жүктеу 14,81 Mb.

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

1 ... 98 99 100 101 102 103 104 105 ... 127