ң . PDA-ұ құғ ң ө қ ң қғ NFA.ғ DFA-da NFA-da ұ қ . қ ғ қ .қ ү : q 
. ә ғ, 
w .M=<k, 
> -- ; k=қ ү ; S 
k-қ ү; F -қ ү; 
:kx 
K; 
:k={ 
}; ={a,b}; S= 
; F={ }
A b a
L={ 
}
19. ң ғ ғ . ң қғ ?
M = (Q, ∑, δ, q0, F) қ ң (NFA) қ ғ ұ үң ө ө ε-ө ұқ .
үң ө ө ? ұ ә қғ ө ү ү . ғ, q ү a ү Q-ң δ(q,a) = {p1, p2, , pk} ө q ү a- қғ p1, p2, , pk ң .
NFA- үң ө ө қ ε-ө қ. ε-ө ң , ә ү ө ү. қ қ, қ қ-қ ү ө .
(PDA) құғ ә ң ө қ- ң қғ қ . қғ ө қ, ңғ ғ, ә қ құғ. ң әқ ң ө қ. : push ә pop.
ң ғ : ң қ қ . ғ, PDA- ө ү қ ғ ң . ң қғ ғ . ʳ ғ :
ω ө a- b- 3 ө ә b- a- . ғ ң қғ қ : ө ү , , ө қ ү .
|
|
|
ұ қ, a A , b 3 A ө. ғ, ү b ү a- 3 !
ғ ө қ қ? Қ ғ ө қ?
қ , ғ NFA қ ғ ө қ? ө қ ң, ғ DFA-ң . , қ үң ө ө ε-ө ұқ . ұ ң ә ұ , ғ ң ө қ қ , ұғ ғ ө, ң , ө қ ү .
, ғ PDA қ ғ ө қ? ө қ ң , . ұ құғ қ . ғ, қ қ өң ң қғ, ө қ.
