Seznam nalezených chyb, nepřesností a překlepů

Automaty a gramatiky. Sbírka řešených příkladů. 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.


Automaty a gramatiky. Sbírka řešených příkladů. 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).

Nápady na vylepšení pro 2. vydání

  • Přidat (více popsat) problém zastavení.
  • Přidat souhrnnou tabulku výpočetní síly DKA, NKA, DZA, NZA, ... (co přijímají a příklady jazyků, které nelze přijmou slabším strojem).
  • U KA, ZA, TS lidsky vysvětlit, co je to konfigurace.
  • Přidat příklady na polynomiální redukci.
  • Přidat do předmluvy odkaz na tyto online errata :)
  • Sekci 3.1.6 přesunou před sekci 3.1.4 (motivace: pořadí transformací bude pak stejné, jako při převodu bezkontextové gramatiky na vlastní).
  • Do sekce 1.1 přidat definici reverzovaného řetězce, palindromu, podřetězce, sekvence, podsekvence, prefixu a suffixu.
  • Do sekce 1.2 (tabulka i text) přidat zmínku o rekurzivních jazycích.
  • Strana 10: Přidat do tabulky sloupec pro rekurzivní jazyky a řádek pro operaci průnik s regulárním jazykem.
  • Úloha 2.1 (a podobné): Předělat font, aby "ě, á, č" vypadaly lépe.
  • Přidat sekci o lexikální analýze.
  • Přidat důkaz, že diagonální jazyk není rekurzivně spočetný.
  • Na str. 60 v úloze 2.68 upravit automat, aby přijímal i 0. Zároveň přidat komentář, že řetězce 0, 00, 000... (reprezentující zápis čísla 0) jsou brány jako validní vstup. 0 je dělitelná číslem 4 beze zbytku.
  • Na str. 113 (Myhill-Nerodova věta) - slovo "deterministický" by mohlo být v závorce, neboť stačí pouze říci, že L je přijímaný konečným automatem.

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?

Vaše osobní údaje budou použity pouze pro účely vyřešení vašeho dotazu.