Turingov stroj in Turingov generator

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Turingov stroj je stroj, s katerim lahko izračunamo vse kar se izračunati da.

Vsebina

1 Turingov stroj
- 1.1 Definicija
  - 1.1.1 Trenutni opis:
  - 1.1.2 Definicija funkcije prehodov (primer):
- 1.2 Primer Turingovega stroja
  - 1.2.1 Brez pomožnih trakov
  - 1.2.2 Z dvema pomožnima trakovama
2 Turingov generator
- 2.1 Definicija
- 2.2 Primer Turingovega generatorja

Turingov stroj

Definicija

Ponavadi je definiran kot sedmerica:

$M = <\mathrm{Q},\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ \mathrm{Bl},\ \mathrm{F}>,\ |\mathrm{Q}|,\ |\Sigma|,\ |\Gamma|\ <\ \infty$

Kjer so:

Q ... množica notranjih stanj avtomata

$Σ$ ... Vhodna abeceda avtomata

$Γ$ ... Tračna abeceda avtomata

$\mathrm{Bl} \in \Gamma$ ... Blank, prazno polje

$\mathrm{F} \subseteq \mathrm{Q}$ ... množica končnih stanj avtomata

$\delta : \mathrm{Q}\ \times \ \Gamma \ \to \ \mathrm{Q} \ \times \ \Gamma \ \times \{ L,\ D \}$ ... funkcija prehodov avtomata

Trenutni opis:

$<\alpha, \ \mathrm{q}, \ \mathrm{B}>\ \in \ \Gamma^* \ \times \ \mathrm{Q} \ \times \ \Gamma^*$

Definicija funkcije prehodov (primer):

$\delta \left ( Trenutno\ stanje,\ Znak\ na\ traku \right ) = <Novo\ stanje,\ Nov\ znak\ na\ traku,\ Smer>$

Primer Turingovega stroja

Sestavi Turingov stroj, ki sprejema jezik oblike:

$L = \{ w\ |\ \sharp a(w)=\sharp b(w),\ w \in \ \{ a,b \}^*$ ... število a-jev je enako številu b-jev

Brez pomožnih trakov

$\delta \left ( q_0,\ a\right ) = <q_1,\ Y,\ D>\qquad \delta \left ( q_0,\ b\right ) = <q_3,\ Y,\ D>$

$\delta \left ( q_1,\ a\right ) = <q_1,\ a,\ D>\qquad \delta \left ( q_3,\ b\right ) = <q_3,\ b,\ D>$

$\delta \left ( q_1,\ X\right ) = <q_1,\ X,\ D>\qquad \delta \left ( q_3,\ X\right ) = <q_3,\ X,\ D>$

$\delta \left ( q_1,\ b\right ) = <q_2,\ X,\ L>\qquad \delta \left ( q_3,\ a\right ) = <q_2,\ X,\ L>$

$\delta \left ( q_2,\ a\right ) = <q_2,\ a,\ L>$

$\delta \left ( q_2,\ b\right ) = <q_2,\ b,\ L>$

$\delta \left ( q_2,\ X\right ) = <q_2,\ X,\ L>$

$\delta \left ( q_2,\ Y\right ) = <q_4,\ Y,\ D>$

$\delta \left ( q_4,\ X\right ) = <q_4,\ X,\ D>$

$\delta \left ( q_4,\ a\right ) = <q_1,\ X,\ D>$

$\delta \left ( q_4,\ b\right ) = <q_3,\ X,\ D>$

$\delta \left ( q_4,\ Bl\right ) = <q_F,\ Bl,\ D>\qquad \delta \left ( q_0,\ Bl\right ) = <q_F,\ Bl,\ D>$

Z dvema pomožnima trakovama

Lahko pa ga definiramo dosti preprosteje z avtomatom, ki ima dva pomožna trakova:

$\delta \left ( q_0,\ Bl,\ Bl,\ Bl\right ) = <q_1,\ Bl,\ /,\ Bl,\ L,\ Bl,\ L>$

$\delta \left ( q_0,\ a,\ Bl,\ Bl\right ) = <q_0,\ a,\ D,\ a,\ D,\ Bl,\ />$

$\delta \left ( q_0,\ b,\ Bl,\ Bl\right ) = <q_0,\ b,\ D,\ Bl,\ /,\ b,\ D>$

$\delta \left ( q_1,\ Bl,\ a,\ b\right ) = <q_1,\ Bl,\ /,\ a,\ L,\ b,\ L>$

$\delta \left ( q_1,\ Bl,\ Bl,\ Bl\right ) = <q_F,\ Bl,\ /,\ Bl,\ /,\ Bl,\ />$

Turingov generator

Definicija

Turingov generator je turingov stroj, ki na trak izpisuje vse besede določenega jezika ločene z znakom #.

Primer Turingovega generatorja

Sestavi turingov generator za jezik:
$\{ 0^n1^n2^n\ |\ n\ge0\}$
$\delta: Q\ \times\ \Gamma\ \rightarrow\ Q\ \times\ \Gamma\ \times\ \{D,/\}\ \times\ \Gamma\ \times\ \{L,D,/\}$
Sestavili bomo TG z enim po možnim trakom.

$\delta(q_0,Bl)\rightarrow<q_1,\sharp,D,X,D>$
$\delta(q_1,Bl)\rightarrow<q_2,Bl,/,Bl,L>$
$\delta(q_2,X)\rightarrow<q_2,0,D,X,L>$
$\delta(q_2,Bl)\rightarrow<q_3,Bl,/,Bl,D>$
$\delta(q_3,X)\rightarrow<q_3,1,D,X,D>$
$\delta(q_3,Bl)\rightarrow<q_4,Bl,/,Bl,L>$
$\delta(q_4,X)\rightarrow<q_4,2,D,X,L>$
$\delta(q_4,Bl)\rightarrow<q_5,\sharp,D,X,D>$
$\delta(q_5,X)\rightarrow<q_5,Bl,/,X,D>$
$\delta(q_5,Bl)\rightarrow<q_2,Bl,/,Bl,L>$