Matfyz Wiki

Zápočet Majerech 7.5.2012, 15:40

gejlord at 2012-05-07 17:32:51

  1. Rozhodněte, zda existuje jazyk L takový, že L i jeho doplněk splňují předpoklady podtrhávacího pumping lemma pro regulární jazyky, ale L není regulární.

  2. Rozhodněte, zda lze každou gramatiku ekvivalentně převést (generuje stejný jazyk) do pravidel tvaru: \alpha X \beta \rightarrow \alpha \gamma \beta{: alt="\alpha X \beta \rightarrow \alpha \gamma \beta" type="image/"}, kde X \in V_N{: alt="X \in V_N" type="image/"} a \alpha, \beta, \gamma \in (V_N \cup V_T)^*{: alt="\alpha, \beta, \gamma \in (V_N \cup V_T)^*" type="image/"}

  3. Sestrojte redukovaný konečný automat přijímající slova tvaru 11(00+11)^*{: alt="11(00+11)^*" type="image/"}, jejichž binární interpretace je dělitelná třemi.

  4. Převeďte do Chomského normální formy:
    S \rightarrow TaL | MRAZ{: alt="S \rightarrow TaL | MRAZ" type="image/"}
    T \rightarrow t | A{: alt="T \rightarrow t | A" type="image/"}
    L \rightarrow a{: alt="L \rightarrow a" type="image/"}
    M \rightarrow MLZ | RYM{: alt="M \rightarrow MLZ | RYM" type="image/"}
    Z \rightarrow az{: alt="Z \rightarrow az" type="image/"}
    Y \rightarrow y{: alt="Y \rightarrow y" type="image/"}
    R \rightarrow RYL | MYL{: alt="R \rightarrow RYL | MYL" type="image/"}
    A \rightarrow aAa | \lambda{: alt="A \rightarrow aAa | \lambda" type="image/"}

První úloha prý byla stejná i pro první skupinu (v 14:00). Ostatní nevim. Taky nám napsal na tabuli znění podtrhávacího pumping lemma.