Turingov stroj
From Wikipedia, the free encyclopedia
Turingov stroj (TS) je jeden z najdôležitejších modelov na opis formálnych jazykov.
Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje. |
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 akceptujúceho stavu.
Usporiadanú 9-ticu nazývame Turingov stroj, kde význam symbolov je:
je konečná množina stavov,
je vstupná abeceda
je pásková abeceda, obsahujúca ako svoju podmnožinu abecedu
je prechodová funkcia,
je počiatočný stav
je ľavá koncová značka
je symbol označujúci prázdne políčko
je akceptujúci stav
je zamietajúci stav
Modifikácie Turingových strojov
- Turingov stroj s 1-smerne nekonečnou páskou.
- m-páskové Turingové stroje.
- Turingové stroje s read-only (R/O) vstupnou páskou a 2 zásobníkmi.
- Počítadlové Turingové stroje.
Existuje viacero variantov Turingovho stroja, napríklad:
- Deterministický TS
- Nedeterministický TS
- Alternujúci TS (paralelne pracujúci)
- k-páskový TS
Turingov stroj rozpoznáva triedu rekurzívne vyčísliteľných jazykov.
Viac informácií Chomskéhohierarchia, Gramatika ...
Formálne jazyky, automaty a gramatiky | |||
---|---|---|---|
Chomského hierarchia |
Gramatika | Jazyk | 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. |
Zavrieť