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

жүктеу 14,81 Mb.

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

1 ... 110 111 112 113 114 115 116 117 ... 127

Теория негізі
Анықтама 5.2.
Алгоритм 5.1.

Зертханалық жұмыс№ 5

Магазинді жадылы автоматтар
Мазмұны: Магазинді жадылы автоматпен КТ-грамматикалардың эквиваленттілігі. Контексті-тәуелсіз грамматика бойынша магазинді жадылы автоматтарды құру.
Мақсаты: - «магазин жадысының автоматы (МП-автомат)», ұғымын қалыптастыру «кеңейтілген МП-автоматы», «МП-автоматының құрылымы»; «МП-автоматоматына жіберілген жол және тіл»;

- КС – грамматика бойынша кеңейтілген МП-автоматының және МП-автоматының құрылымын құруға, МП-автоматының көмегімен енгізу жолының талдалуы.

Теория негізі

КС-тілдерін магазин жадысы бар автомат арқылы тануға болады (МП-автомата).

Анықтама 5.1. МП-автоматын жеті түрінде ұсынуға:

M = (Q,T,N,F,q_0tN₀,Z), (5.1)

мұнда Q – автомат қалпының соңғы көптігі;

T- соңғы енгізу алфавиті;

N-соңғы магазин алфавиті;

F – көптікті бейнелейтін, магазиндік функция )(Q × (T ∪ {ε}) × N

Жиын барлық ішкі жиындарының жиынына QxN , бұл дегеніміз.

F: (Q×(T{_ε})×N)→P(Q×N*);

q₀ – автоматтың бастапқы қалпы, q₀ Q;

N₀- магазиннің бастапқы символы, N₀ Т;

Z – автоматтың соңғы қалпының көптігі, Z Q.

Анықтама 5.2. МП-автоматтың кескін үйлесімі үш түрі болады:

(q,a>,a)c(QxT*xN*), (5.2)

мұнда q – автоматтың ағымдағы қалпы, q Q;

со – енгізу жолының бөлігі, оның бірінші символы енгізу басының

астында орналасқан, ωT* ;

α – магазин құрамы, aN _*

М

П-автоматының жалпы схемасы 5.1. суретте көрсетілген
Сурет 5.1 - МП-автоматтың схемасы Алгоритм 5.1.

жүктеу 14,81 Mb.

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

1 ... 110 111 112 113 114 115 116 117 ... 127