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.

Úloha 2.2, ve výsledné gramatice je v množině terminálních symbolů dvakrát uveden symbol "r".

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".

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ý.

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í).

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}.

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.

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)*.

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.

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.

V úloze 3.17 chybí v gramatice G v množině terminálních symbolů symbol "c".

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

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.

V úloze 3.30 je ve výsledné gramatice G' duplicitní pravidlo A->C.

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.

V definici neterminálního symbolu rekurzivního zleva by místo "=>*" mělo být "=>+".

Š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.

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.

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.

"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.

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).

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).