navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m36tpj:zapisky [2012/01/12 16:59] woxie2 |
courses:a4m36tpj:zapisky [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 21: | Řádek 21: | ||
| * Stav, ve kterém se může program nacházet (čili v případě aritmetických výrazů všechny možné kombinace jako (1+2), (2+1), (2+(5*6)+3), ...). Konfigurací tedy může být (a většinou i je) nekonečně mnoho. | * Stav, ve kterém se může program nacházet (čili v případě aritmetických výrazů všechny možné kombinace jako (1+2), (2+1), (2+(5*6)+3), ...). Konfigurací tedy může být (a většinou i je) nekonečně mnoho. | ||
| * u PostFixu je to (CommandSeq, Stack) | * u PostFixu je to (CommandSeq, Stack) | ||
| + | * DEF EN: Each state of the abstract machine is called a configuration. | ||
| ==== Přepisovací funkce ==== | ==== Přepisovací funkce ==== | ||
| Řádek 28: | Řádek 29: | ||
| ==== Finální konfigurace ==== | ==== Finální konfigurace ==== | ||
| * u PostFixu je to ([], S) -> již není s čím pracovat, množina příkazů je prázdná | * u PostFixu je to ([], S) -> již není s čím pracovat, množina příkazů je prázdná | ||
| - | * Finální konfigurace je konfigurace, která se již nemůže přepsat pomocí přepisovacího pravidlo (neexistuje na ní přepisovací pravidlo) | + | * Finální konfigurace je konfigurace, která se již nemůže přepsat pomocí přepisovacího pravidla (neexistuje pro ni přepisovací pravidlo) |
| - | * Pro finální konfiguraci existuje výstup z výstupní funkce OF | + | * Pro finální konfiguraci existuje výstup z výstupní funkce OF |
| ==== Stuck state ==== | ==== Stuck state ==== | ||
| * Je stav, který nelze dále přepsat, ale zároveň pro něj výstupní funkce OF nemá žádný výstup | * Je stav, který nelze dále přepsat, ale zároveň pro něj výstupní funkce OF nemá žádný výstup | ||
| * Dá se odstranit tím, že výstupní funkci předefinujeme přidáním stavu error | * Dá se odstranit tím, že výstupní funkci předefinujeme přidáním stavu error | ||
| - | * Př: [pop, ε] | + | * Př: [pop, ε] //příkaz pop na prázdném zásobníku// |
| - | * Př odstranění: Postfixový stav se přepíše na chybový výstup,[pop, ε] -> error | + | * Př odstranění: Postfixový stav se přepíše na chybový výstup, [pop, ε] -> error, po této úpravě se stav [pop, ε] změní ze stuck state na finální konfiguraci |
| ==== Operační sémantika ==== | ==== Operační sémantika ==== | ||
| Řádek 173: | Řádek 174: | ||
| ===== Quicksort ===== | ===== Quicksort ===== | ||
| - | Dokuwiki neumí matematickou syntaxi, takže ε je epsilon a · je symbol zřetězení. | + | malé epsilon - ε je prázdná množina a · je symbol zřetězení. |
| ==== Zápis relací ==== | ==== Zápis relací ==== | ||
| Řádek 222: | Řádek 223: | ||
| MSORT(A) -> A if len(A) = 1 | MSORT(A) -> A if len(A) = 1 | ||
| - | D-> MSORT(B)·MSORT(C) pro všechny x ∈ B: pro všechny y ∈ C: x < y | + | MSORT(B)·MSORT(C) -> D pro všechny x ∈ B: pro všechny y ∈ C: x < y |
| ----------------------------------------------------------- | ----------------------------------------------------------- | ||
| MSORT(A) -> D | MSORT(A) -> D | ||
