Zápočtový test

Studijní materiály Praktické otázky Konečný automat Regulární výraz Další praktické otázky Teoretické otázky Důkaz neregularity Důkaz nebezkontextovosti Další teoretické otázky

Studijní materiály

Praktické otázky

Konečný automat

základní KMP automat
průnik a rozdíl automatů
determinizace a redukce automatu

Regulární výraz

konstrukce automatu podle regulárního výrazu
konstrukce regulárního výrazu podle popisu přijímaných slov
konstrukce regulárního výrazu na základě konečného automatu

Další praktické otázky

zařazení jazyka slov tvaru $b|k^T$ $b ∣ k^{T}$ , kde $b$ $b$ je binární zápis čísla a $k$ $k$ je zápis téhož čísla v konkrétní číselné soustavě, do Chomského hierarchie
- někdy je jazyk kontextový (monotónní), jindy i bezkontextový (v závislosti na vztahu číselných soustav)
- čtyřková jde bezkontextově, jedničková a trojková jdou kontextově (monotónně)
převod bezkontextové gramatiky do Chomského normální formy
- Chomského normální forma – povolená jsou pouze pravidla ve tvaru $X\to YZ$ $X \to Y Z$ nebo $X\to a$ $X \to a$ , přičemž lze deklarovat $\lambda\in L$ $λ \in L$
  - kde $\lambda$ označuje prázdné slovo
- moc dlouhá pravidla řešíme nadtrháváním
- dlouhá pravidla s terminály řešíme přidáním odpovídajících neterminálů
- pravidlo typu $T\to U$ musíme převést náhradou $U$ pravými stranami pravidel s $U$ na levé straně
- pro pravidlo tvaru $U\to\lambda$ $U \to λ$ musíme pravidlo $T\to UV$ $T \to U V$ upravit na $T\to UV\mid V$ $T \to U V ∣ V$
  - tady vzniklo problematické pravidlo $T\to V$ , ale to řešíme způsobem uvedeným výše
převod monotónní gramatiky do kontextového tvaru
- např. $AB\to CD$ převedeme na $AB\to\bar AB\to\bar A\bar B\to C\bar B\to CD$
- pokud by se mezi jednotlivé kroky přepisování vloudila nějaká pravidla operující se znaky z této dvojice, mohli bychom je přesunout před první krok nebo za poslední krok
jazyk slov s mocninným počtem písmen
- nejde bezkontextově, existuje monotónní gramatika

Teoretické otázky

Důkaz neregularity

pumping lemma
- nechť $L$ je regulární jazyk
- $(\exists n\in\mathbb N)(\forall w\in L):|w|\geq n\implies w=\alpha\beta\gamma$ $(\exists n \in N) (\forall w \in L) : ∣ w ∣ \geq n ⟹ w = α β γ$
  - $|\beta|\gt 0$
  - $|\alpha\beta|\leq n$
  - $\forall t\geq 0:\alpha\beta^t\gamma\in L$
- jelikož je $L$ $L$ regulární, existuje automat $A$ $A$ rozpoznávající $L$ $L$
  - za $n$ zvolíme počet stavů tohoto automatu
- k důkazu neregularity $L_{01}=\set{0^k1^k\mid k\in\mathbb N}$ $L_{01} = {0^{k} 1^{k} ∣ k \in N}$ použijeme slovo $w=0^n1^n$ $w = 0^{n} 1^{n}$ , kde $n$ $n$ je konstanta z lemmatu
  - $|\alpha\beta|\leq n\implies 1\notin\alpha\beta$
  - slovo $\alpha\beta^t\gamma$ pro $t\neq 1$ má jiný počet nul než jedniček, tedy nepatří do jazyka, což je spor
uzávěrové vlastnosti
- mějme regulární jazyky $L,M$ $L, M$ , pak $L\cup M$ $L \cup M$ , $L\cap M$ $L \cap M$ , $L-M$ $L - M$ a $\overline L$ $\overline{L}$ jsou také regulární
  - kde $\overline L=\Sigma^*-L$ (doplněk)
- důkaz neregularity jazyku slov se stejným počtem nul a jedniček
  - jazyk slov $0^*1^*$ je zjevně regulární
  - průnik těchto dvou jazyků je neregulární jazyk $L_{01}$
- podobně umíme odvodit, že jazyk slov s různým počtem nul a jedniček není regulární a že jazyk slov tvaru $0^i1^j$ , kde $i\neq j$ není regulární

Důkaz nebezkontextovosti

pumping lemma pro bezkontextové jazyky
- nechť $L$ je bezkontextový jazyk
- $(\exists n)(\forall w\in L):|w|\geq n\implies w=u_1u_2u_3u_4u_5$ $(\exists n) (\forall w \in L) : ∣ w ∣ \geq n ⟹ w = u_{1} u_{2} u_{3} u_{4} u_{5}$
  - $\forall k\geq 0:u_1u_2^ku_3u_4^ku_5\in L$
  - $|u_2u_3u_4|\leq n$
  - $|u_2u_4|>0$
uzávěrové vlastnosti
- bezkontextové jazyky jsou uzavřené na sjednocení, konkatenaci, iterace, pozitivní iterace, zrcadlový obraz

Další teoretické otázky

podtrhávací pumping lemma
- dvě varianty – pro regulární i bezkontextové jazyky
- obecně místo délek slov počítáme počty podtržených písmen (všechny „absolutní hodnoty“ ve lemmatech takto nahradíme)
- pro CFL asi Ogdenovo lemma?
normální formy gramatik
- $\mathcal L_0$ $L_{0}$ … $\alpha\chi\beta\to\alpha\gamma\beta$ $α χ β \to α γ β$
  - $\alpha,\beta\in (V_N\cup V_T)^*$
  - $\chi\in V_N$
  - $\gamma\in (V_N\cup V_T)^*$
- $\mathcal L_1$ $L_{1}$ … $\alpha\chi\beta\to\alpha\gamma\beta$ $α χ β \to α γ β$
  - $\alpha,\beta\in(V_N\cup V_T)^*$
  - $\chi\in V_N$
  - $\gamma\in (V_N\cup V_T)^+$
- $\mathcal L_2$ $L_{2}$ … $X\to YZ\mid a$ $X \to Y Z ∣ a$
  - $X,Y,Z\in V_N$
  - $a\in V_T$
- $\mathcal L_3$ $L_{3}$ … $X\to aY\mid\lambda$ $X \to aY ∣ λ$
  - $X,Y\in V_N$
  - $a\in V_T$
dvoucestný konečný automat vs. jednocestný konečný automat
- stejně silné
dvoucestný zásobníkový automat vs. jednocestný zásobníkový automat
- existuje dvoucestný přijímající $0^n1^n2^n$ , jednocestný nikoliv
vztah mezi bezkontextovými gramatikami a jazyky přijímanými nedeterministickými zásobníkovými automaty prázdným zásobníkem
- viz prezentace