МП-автоматының жұмыс жасауы
МП-автоматының бастапқы конфигурациясы (q0, ω, N0) болады.
МП-автоматының жұмыс қадамын қатынас түрінде ұсынамыз («|=» былай белгілейміз) және қатынастардың қол жетерлігімен ( «|=*» былай белгілейміз). Егер магазин функцияларының мағыналарының біреуі )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.
Достарыңызбен бөлісу: |