Turingov stroj

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Turingov stroj (TS) je jeden z najdôležitejších modelov na opis formálnych jazykov.

Stroj dostane na vstup zapísané vstupné slovo na páske, hlava stojí nad prvým políčkom. Páska je dostatočne dlhá (hovorí sa že je nekonečne dlhá). Stroj sa nachádza v počiatočnom stave. Podľa prechodovej funkcie pracuje na vstupnom slove, pričom jednotlivé symboly môže aj prepisovať. Stroj akceptuje slovo, ak sa dostane do stavu z množiny koncových stavov.

Usporiadanú šesticu nazývame Turingov stroj, kde význam symbolov je:

  • je množina stavov,
  • je vstupná abeceda
  • je pásková abeceda
  • je prechodová funkcia,
  • je počiatočný stav
  • je množina koncových stavov

Modifikácie Turingových strojov

Existuje viacero variantov Turingovho stroja, napríklad:

Turingov stroj rozpoznáva triedu rekurzívne vyčísliteľných jazykov.

Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.