Tři
typy přijímaných jazyků: Ekvivalence
Tvrzení:
•L = L(Mf)f pro ZA Mf Û L = L(Mfe)fe pro ZA Mfe
•L = L(Me)e pro ZA Me Û L = L(Mfe)fe pro
ZA Mfe
•L = L(Mf)f pro
ZA Mf Û L = L(Me)e pro
ZA Me
Pozn. Existují algoritmy pro následující převody:
ZA Mfe, který přijímá L přechodem do koncového stavu a vyprázdněním zásobníku
ZA Mf , který přijímá L přechodem do konc. st.
ZA Me, který
přijímá L vyprázdněním zásobníku
31/50