Uživatelské nástroje
msz:turingovy_stroje
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verze | |||
| msz:turingovy_stroje [16. 06. 2012, 15.38:04] – pitel | msz:turingovy_stroje [15. 08. 2026, 14.10:54] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1 | ||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Turingovy stroje | ||
| - | [[wp> | ||
| - | //M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, // | ||
| - | * //Q// -- konečná množina stavů | ||
| - | * //Σ// -- konečná vstupní abeceda, //Δ// ∉ //Σ// | ||
| - | * //Γ// -- konečná pásková abeceda, //Σ// ⊂ //Γ//, //Δ// ∈ //Γ// | ||
| - | * //δ// -- parciální přechodová funkce, //δ//: (//Q// \ {// | ||
| - | * //q//₀ -- počáteční stav, //q//₀ ∈ //Q// | ||
| - | * // | ||
| - | |||
| - | Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky! | ||
| - | ===== Jazyky přijímané TS ===== | ||
| - | Množina všech řetězců v obsahu pásky ve vstupní konfiguraci pro které TS normálně zastaví. | ||
| - | |||
| - | * Úplný Turingův stroj((vždy zastaví)) ⇔ rekurzivní jazyk | ||
| - | * Turingův stroj ⇔ rekurzivně vyčíslitelný jazyk | ||
| - | |||
| - | Speciálním případem TS jsou linárně omezené automaty (LOA), je to vlastně TS ale s konečnou páskou, a dokáží přijímat kontextové jazyky | ||
| - | ===== Varianty TS ===== | ||
| - | **Úplný TS** vždy zastaví. | ||
| - | ==== Lineárně omezené automaty ==== | ||
| - | TS s omezenou páskou. Přijímá kontextové jazyky. | ||
| - | ==== Univerzální TS ==== | ||
| - | Umí interpretovat jiné TS. Na vstupu se nějak (pomocí '' | ||
/var/www/wiki/data/attic/msz/turingovy_stroje.1339861084.txt.gz · Poslední úprava: (upraveno mimo DokuWiki)
Nástroje pro stránku
Kromě míst, kde je explicitně uvedeno jinak, je obsah této wiki licencován pod následující licencí: CC Attribution-Share Alike 4.0 International
