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

МП-автоматының жұмыс жасауы

жүктеу 14,81 Mb.

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

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

МП-автоматының жұмыс жасауы

МП-автоматының бастапқы конфигурациясы (q₀, ω, N₀) болады.

МП-автоматының жұмыс қадамын қатынас түрінде ұсынамыз («|=» былай белгілейміз) және қатынастардың қол жетерлігімен ( «|=*» былай белгілейміз). Егер магазин функцияларының мағыналарының біреуі )F(q Q,t (T{ε}),S N болса )(q^′ Q,γN *, онда жазылады )(q, tω, Sα) |= (q^′, ω, γα. Осыдан келесі нұсқалар болуы мүмкін.

1) Жағдай t T. Автомат q қалпының ағымында болып тұр, енгізу t, символын оқиды, стектың басында Sсимволы бар. Олкелесі q^′, қалыпқа өтеді, енгізу басын бір ұяшыққа оңға қарай жылжытады және жоғарғы S символын γ жолына магазинн символына жылжытады. γ = ε бұл дегеніміз, S стектан жойылады.

2) Жағдай t = ε. Бірінші жағдайдан айырмашылығы, енгізу t символына көңіл бөлінбейді және енгізу басы жылжымайды. МП-автоматының бұндай жұмыс қадамы ε -қадамы деп аталады, ол енгізужолының оқылуы аяқталса да орындалуы мүмкін.

МП-автоматының соңғы конфигурациясы (q, ε, α) конфигурациясы болады, мұнда q Z.

жүктеу 14,81 Mb.

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

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