next up previous
Next: About this document ...

A megoldás gondolatmenete a következő:
három fázis van, az elsőben a-k jönnek, a másodikban b-k, a harmadikban c-k. Az első fázisban feltöltjük a vermet A-kal, minden újabb érkező a betesz egy új A-t a verembe. A b-k hatására kiszedjük az A-kat, amíg el nem fogynak és amikor elfogytak, akkor B-ket rakunk bele. Ha jönnek a c-k, akkor meg elkezdjük kiszedni a B-ket és ha a B-k épp akkor fogynak el a veremből, amikor a c-k is a szalagról, akkor a szó jó.
Az állapotok azért kellenek (és itt volt a kavarodás az órán), hogy ne fordulhasson elő az, hogy például b után még a jön az inputon.
Arra kell még figyelni, hogy lehet, hogy a szó b-vel kezdődik vagy az is lehet, hogy b-re végződik, meg az is lehet, hogy az $\epsilon$-ról van szó. Ezt is kezelni kell tudni (az utolsó három szabály a következő leírásban).

Szabályokkal: $\delta(q_0,a,Z_0)=(q_a,AZ_0)$, $\delta(q_a,a,A)=(q_a,AA)$, $\delta(q_a,b,A)=(q_b,\epsilon)$, $\delta(q_b,b,A)=(q_b,\epsilon)$, $\delta(q_b,b,Z_0)=(q_b,BZ_0)$, $\delta(q_b,b,B)=(q_b,BB)$, $\delta(q_b,c,B)=(q_c,\epsilon)$, $\delta(q_c,c,B)=(q_c,\epsilon)$, $\delta(q_c,\epsilon,Z_0)=(q_F,\epsilon)$, $\delta(q_0,b,Z_0)=(q_b,BZ_0)$, $\delta(q_b,\epsilon,Z_0)=(q_F,\epsilon)$, $\delta(q_0,\epsilon,Z_0)=(q_F,\epsilon)$,



 

Judit Csima
2000-03-29