cviceni

ve výsledných slovech jsou jen terminály

• $\mathcal L_0$ gramatiky
  • normální forma
    • $\alpha\chi\beta\to\alpha\gamma\beta$
      • $\alpha,\gamma,\beta\in (V_N\cup V_T)^*$
      • $\chi\in V_N$
• $\mathcal L_1$ monotónní gramatiky
  • $|L_i|\leq |P_i|$
    • slova se nemůžou zkracovat
  • deklarace $\lambda\in L$
    • kde $\lambda$ je prázdné slovo
  • normální forma
    • $\alpha\chi\beta\to\alpha\gamma\beta$
      • $\alpha,\beta\in(V_N\cup V_T)^*$
      • $\gamma\in (V_N\cup V_T)^+$
      • $\chi\in V_N$
• $\mathcal L_2$ bezkontextové gramatiky
  • $|L_i|=1$
  • Chomského normální forma
    • $X\to YZ\mid a$
      • $X,Y,Z\in V_N$
      • $a\in V_T$
      • tzn. na levé straně jeden neterminál, na pravé straně dva neterminály nebo jeden terminál
    • navíc tam patří prázdné slovo (tzn. deklarujeme $\lambda\in L$)
      • lze obejít složitým způsobem (bez deklarace)
• $\mathcal L_3$ regulární gramatiky
  • $X\to Yw\mid w$
    • $X,Y\in V_N$
    • $w\in V_T^*$
  • normální forma
    • $X\to Ya\mid\lambda$
      • $X,Y\in V_N$
      • $a\in V_T$
  • možná lepší varianta je místo $Yw$ uvažovat $wY$ apod.

• zjevně $\mathcal L_3\subseteq\mathcal L_2$
• pro $\mathcal L_2\subseteq \mathcal L_1$
  • máme
    • $X\to\lambda\mid a$
    • $Y\to XZb$
  • převedeme na
    • $X\to a$
    • $Y\to XZb\mid Zb$
    • (vyškrtli jsme $X\to\lambda$)
  • to nestačí
    • mohli bychom se zacyklit
    • budeme si značit, které neterminály už jsme vyškrtli
    • nebo to můžeme udělat najednou (poznačíme si všechny levé strany, které mají napravo $\lambda$)
• zjevně $\mathcal L_1\subseteq\mathcal L_0$
• k ostrosti se vrátíme

• kontrolují, že na vstupu je slovo z gramatiky
• (3) konečné automaty
  • automatu odpovídá jazyk, který dostaneme ze všech slov, které začínají v šipkách dovnitř a končí v šipkách ven
  • deterministický vs. nedeterministický
  • přechodové hrany s písmenky
  • slovo rozložíme na několik hran
  • prázdné slovo vyřešíme zdvojením šipek
  • $X\to aY$ v automatu zapíšeme jako $X\xrightarrow{a}Y$
• (2) zásobníkové automaty
  • přepisovací pravidla lze zapisovat jako strom a číst listy v inorder pořadí
  • fungují nedeterministicky
• (1) Turingovy stroje, které se nepohybují mimo vstupní pásku
  • běžíme proti směru generování – zkracuje se to
• (0) Turingovy stroje

• na levé straně se nesmí vyskytovat terminály nebo musí vyskytovat aspoň jeden neterminál
• to se dá zařídit tak, že terminál $a$ nahradíme terminálem $\overline a$ a přidáme další přepisovací pravidlo $\overline a\to a$