9. gyakorlat

Röpzh megoldása

\(F = x \lor y \to \neg y \lor z \to \neg x \land z\)

knf: \((\neg x \lor \neg y \lor \neg z) \land (\neg x \lor y \lor \neg z) \land (\neg x \lor y \lor z)\)

Turing gépek

Hasonló a korábban tanult véges és verem automatákhoz

\(M = (Q,\; \Sigma,\; \Gamma,\; \delta,\; q_0,\; q_i,\; q_n)\)

\(Q\): Az állapotok halmaza \((3 \leq |Q| \leq + \infin)\)

\(q_0, q_i, q_n \in Q\)

• Kezdőállapot
• Elfogadó állapot
• Elutasító állpot

\(\Sigma\): input abc

\(\Gamma\): szalag abc

\(\delta\): átmenet függvény

A számítás nem addig tart, amíg végig nem olvasta a szót, hanem amíg elfogadó vagy elutasító állapotba nem ért.

Diagram értelmezés

• Átmenet függvény diagram
• A diagramokon a tálka jel az üres karakter
• Lépések:
  • L: balra lépünk a szóban
  • R: jobbra lépünk a szóban
• ezt olvastuk | erre cseréljük, erre lépünk
  • (pl.: a | b, R)

Feladat 1

TODO: leírni és belinkelni

Feladat 2

(A \(\_\) jelzi most a tálkát.)

\(\Sigma: \{a, b\}\)

\(\Gamma: \{a, b, \_, X\}\)

\(q_1\) és \(q_2\) elmegy a szó jobb szélére

A \(q_3\) funciója, hogy elmegy a szó bal szélére

Két szalagos turing gép

elsőről olvastuk, másodikról olvastuk | elsőt erre cseréljük, másodikat erre cseréljük, első erre lép, második erre lép

pl.: a, b | c, d, R, L

Feladat 3

Ismerjük fel, hogy ugyanannyi a és b van-e a szóban. Használjunk több szalagot.

Ha a-t olvasunk, akkor ráírjuka második szalagra, ha b-t, akkor elmegyünk a jobb szélére. Ha üres, akkor "fordulunk".

Ha a-t és b-t olvasunk egyszerre a két szalagon, akkor mindkettőn képünk. Ha az elsőn van a, akkor tovább megyünk.

Akkor jó, ha mindkettőn üreset olvasunk. Akkor tudjuk elfogadni.