Errata

AUTOMATY A GRAMATIKY: SBÍRKA ŘEŠENÝCH PŘÍKLADŮ (ČESKÁ VERZE)

3. dotisk 1. vydání (2020)

V tomto dotisku jsou opraveny všechny níže uvedené chyby a nepřesnosti, které byly v 1. vydání a jeho prvním a druhém dotisku.

  • str. 62 (příklad 2.68)
    Konečný automat pro první jazyk by měl podle zadání přijímat i řetězec "0". Aktuálně automat pro M1 přijímá variantu jazyka L1, ve které je podmínka |w| > 0 vyměněna za podmínku |w| > 1.

1. vydání a jeho 1. a 2. dotisk (2017, 2018, 2019)

  • Strana 16:
    Úloha 2.2, ve výsledné gramatice je v množině terminálních symbolů dvakrát uveden symbol "r".
  • Strana 17:
    Horní šedivý rámeček popisující vytvoření regulární gramatiky generující součin jazyků. Nefunguje pro případy, kdy gramatika G2 obsahuje pravidlo S2 -> epsilon.

    Úloha 2.3, ve výsledné gramatice je v množině terminálních symbolů dvakrát uveden symbol "r".
  • Strana 24:
    První dvě tabulky DKA mají dva počáteční stavy. Správně by v obou tabulkách měl stav B být pouze koncový.
  • Strana 35:
    V úloze 2.35 má být napsáno, že výsledný automat je deterministický (ne nedeterministický, ačkoli to není špatně, jen je to matoucí).
  • Strana 75:
    V úloze 2.103, řešení pomocí postupné konstrukce je nesprávně uvedená abeceda u automatu pro elementární regulární vyraz "b". Místo {a} by zde mělo být {b}.
  • Strana 75:
    Od ZS 2020/2021 se postupné konstrukce učí trochu jinak než tomu bylo dříve. Nyní má výsledný automat při skládání vždy pouze jeden koncový stav. Nový postup viz obrázek níže.
  • Strana 85:
    Výsledné řešení úlohy 2.113 by nemělo obsahovat symbol "b" na konci výrazu. Správně tedy: V=(ab+aa(a+b)*b)*.
  • Strana 117:
    V úloze 2.156 krok 2(c) by za symbolem implikace mělo být: a^i b^i není ekvivalentní s a^j b^i.
  • Strana 118:
    V úloze 2.157 je chybně zvolený řetězec u, neboť každý řetězec z jazyka musí obsahovat alespoň jednu jedničku. Správně u=12^(i-1)000.
  • Strana 130:
    V úloze 3.17 chybí v gramatice G v množině terminálních symbolů symbol "c".
  • Strana 131:
    V úloze 3.20 je chybně navržená gramatika. Lze opravit například takto:
    S -> bS | Sa | Sb | ASB | cB
    A -> bA | Ab | a 
    B -> aB | Ba | bB | Bb | b
  • Strana 134:
    V úloze 3.26 je chybně navržená gramatika. Tato gramatika negeneruje řetězce, kde část w obsahuje pouze symboly b (a žádný symbol a). Lze opravit například přidání pravidla W->epsilon.
  • Strana 137:
    V úloze 3.30 je ve výsledné gramatice G' duplicitní pravidlo A->C.
  • Strana 142:
    Druhý šedivý rámeček, první krok. Při převodu na vlastní gramatiku provedeme úpravy v následujícím pořadí: odstraníme epsilon-pravidla, jednoduchá pravidla a pak zbytečné symboly. Můžeme zbytečné symboly odstranit i na začátku (jako první úpravu), ale pak je třeba ještě na závěr (po odstranění epsilon pravidel a jednoduchých) zkontrolovat, zdali se během úprav nevytvořily nějaké další zbytečné symboly.
  • Strana 142:
    V definici neterminálního symbolu rekurzivního zleva by místo "=>*" mělo být "=>+".
  • Strana 145
    Šedivý rámeček, první krok. Při převodu na vlastní gramatiku provedeme úpravy v následujícím pořadí: odstraníme epsilon-pravidla, jednoduchá pravidla a pak zbytečné symboly. Můžeme zbytečné symboly odstranit i na začátku (jako první úpravu), ale pak je třeba ještě na závěr (po odstranění epsilon pravidel a jednoduchých) zkontrolovat, zdali se během úprav nevytvořily nějaké další zbytečné symboly.
  • Strana 154:
    Tvrzení "bezkontextové jazyky definujeme jako jazyky přijímané nedeterministickým zásobníkovým automatem" může být matoucí. V předmětu BI-AAG definujeme bezkontextové jazyky jako jazyky generované bezkontextovou gramatikou. Fakt, že bezkontextové jazyky jsou přijímány nedeterministickými zásobníkovými automaty je tedy formálně vzato pouze důsledek této definice, který lze dokázat.
  • Strana 169:
    V úloze 3.64 je při analýze řetězce w první položka trojice stav "0", ale správně by zde měl být stav "q". V úloze 3.65 je při analýze řetězce w první položka stav "0" (případně "1" na konci), ale správně by zde měl být stav "q" (a stav "r" na konci). Navíc je zde v této úloze na konci prvního řádku analýzy chybně uskočený symbol "a" jako dolní index.
  • Strana 177:
    "Překlad definovaný překladovým zásobníkovým automatem" (ve skriptech je slovo automat). "Řetězec x z oboru hodnot je překladem řetězce w z definičního oboru právě tehdy, když automat příjme řetězec x a přitom na výstup pošle řetezec w." Značení x,w je naopak. Správně: Řetězec w z oboru hodnot je překladem řetězce x z definičního oboru právě tehdy, když automat přijme řetězec x a přitom na výstup pošle řetězec w.
  • Strana 186 + 187:
    První šedivý rámeček na str. 186: "Turingův stroj se zastaví právě tehdy, když přejde do koncového stavu. V nekoncovém stavu se Turingův stroj nikdy nezastaví." Toto je pravda, pokud má daný TS úplně určenou přechodovou funkci. Pokud je přechodová funkce parciální, pak se TS může zastavit i v nekoncovém stavu (pokud z daného stavu nelze použít žádný přechod).
    Poslední šedivý rámeček na str. 187: "Pro řetězec w, které nejsou z L: Turingův stroj přejde do koncového stavu (zastaví se), ale páska není po ukončení výpočtu prázdná (není vyplněna prázdnými symboly B). " Toto je pravda, pokud má daný TS úplně určenou přechodovou funkci. Pokud je přechodová funkce parciální, pak se TS pro řetězce, které nejsou z jazyka, může zastavit i mimo koncový stav (kde skončí s chybou).
  • Strana 192:
    Polynomiální redukce (dovysvětlení): Máme nějakou instanci problému A a víme o ní, zdali je to ano- či ne- instance. Tuto instanci jsme v polynomiálním čase schopni převést na instanci problému B, která bude mít stejnou pravděpodobnostní hodnotu (tedy pokud výchozí instance problému A byla ano-instance, pak výsledná instance problému B je též ano-instance, obdobně pro ne-instance).

    Zároveň platí následující: Když máme polynomiální redukci, která redukuje problém A na problém B, pak A je "lehčí nebo stejně těžký" problém jako B. Redukujeme vždy na problém, který je" alespoň tak těžký" jako náš výchozí problém. Pokud tedy A umíme polynomiálně redukovat na B a zároveň pokud je B řešitelné v polynomiálním čase, pak je i A řešitelné v polynomiálním čase (neboť A je nejvýše tak těžké jako B).

Nenašli jste, co jste hledali? Máte nějaké nápady na vylepšení? Přišlo vám něco nesrozumitelné nebo vám ve sbírce něco chybělo?