Zápočtový test: kartičky | automaty-gramatiky

Praktické otázky

zařazení jazyka slov tvaru $b|k^T$ , kde $b$ je binární zápis čísla a $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ě)

Praktické otázky

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

Praktické otázky

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

Praktické otázky

jazyk slov s mocninným počtem písmen

nejde bezkontextově, existuje monotónní gramatika

Teoretické otázky

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

Teoretické otázky

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í

Teoretické otázky

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$

Teoretické otázky

uzávěrové vlastnosti

bezkontextové jazyky jsou uzavřené na sjednocení, konkatenaci, iterace, pozitivní iterace, zrcadlový obraz

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?

Teoretické otázky

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$

Teoretické otázky

dvoucestný konečný automat vs. jednocestný konečný automat

stejně silné

Teoretické otázky

dvoucestný zásobníkový automat vs. jednocestný zásobníkový automat

existuje dvoucestný přijímající $0^n1^n2^n$ , jednocestný nikoliv

Teoretické otázky

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