====== AP10, IN10 Bezkontextové jazyky ======

===== Zadání =====
(definice, vlastnosti, způsoby jejich reprezentace, konstrukce bezkontextové gramatiky a zásobníkového automatu, normální formy bezkontextových gramatik, použití lematu o vkládání pro bezkontextové jazyky, uzávěrové vlastnost//i// bezkontextových jazyků)

===== Definice =====
 Jazyk <math>L</math> je bezkontextový, pokud existuje bezkontextová gramatika <math>G</math> taková, že <math>L(G)=L</math>.((Přitom každá regulární gramatika je současně i bezkontextová, tedy pouhé nalezení bezkontextové gramatiky ještě nemusí znamenat, že jazyk není navíc i regulární.)) Bezkontextová gramatika (CFG) <math>G</math> je čtveřice <math>(N, \Sigma, P, S)</math>, kde:
  * <math>N</math> je neprázdná konečná množina neterminálních symbolů
  * <math>\Sigma</math> je konečná množina terminálních symbolů taková, že <math>N \cap \Sigma = \emptyset</math>
  * <math>P \subseteq N \times V^\ast</math> je konečná množina pravidel (<math>V = N \cup \Sigma</math>)
  * <math>S \in N</math> je počáteční neterminál

Současně třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.  Tj. jazyk <math>L</math> je bezkontextový, pokud je akceptován nějakým zásobníkovým automatem (existuje zásobníkový automat <math>M</math>, takový, že <math>L(M)=L</math>).

Definici zásobníkového automatu je možné nalézt v otázce [[home:inf:ap11|AP11,IN11 Zásobníkové automaty]]

===== Způsoby reprezentace bezkontextových jazyků =====
Bezkontextové jazyky lze reprezentovat:
  * bezkontextovou gramatikou
  * zásobníkovým automatem
  * rozšířeným zásobníkovým automatem

<note important>
Rozdíl mezi zásobníkovým automatem a rozšířeným zásobníkovým automatem je následující: Zásobníkový automat má přechodovou funkci <math>\delta</math> definovanou jako zobrazení z <math>Q \times (\Sigma \cup \{ \epsilon \}) \times \Gamma</math> do konečných podmnožin množiny <math>(Q\times \Gamma^\ast)</math>. Oproti tomu rozšířený zásobníkový automat má definovanou rozšířenou přechodovou funkci <math>\delta</math> jako zobrazení z konečné podmnožiny množiny <math>Q \times (\Sigma \cup \{ \epsilon \}) \times \Gamma^\ast </math> do konečných podmnožin množiny <math>(Q\times \Gamma^\ast )</math>.

Neformálně řečeno, rozšířený zásobníkový automat "vidí" hlouběji do zásobníku – tj. čte 0--//n// vrchních symbolů.
</note>


===== Konstrukce bezkontextové gramatiky a zásobníkových automatů =====

Konstrukce zásobníkových automatů jsou popsány v otázce [[home:inf:ap11|AP11,IN11 Zásobníkové automaty]].  
Každou bezkontextovou gramatiku, která reprezentuje neprázdný bezkontextový jazyk, lze dále upravit do tzv. kanonických tvarů - lépe se s nimi pracuje, jsou přehlednější, vyžadují je některé algoritmy atd. Kanonické tvary bezkontextových gramatik jsou následující:
  * redukované CFG
  * gramatiky bez <math>\epsilon</math>-pravidel
  * gramatiky bez jednoduchých pravidel
  * gramatiky bez levé rekurze

<box 95% green round|Definice 3.7>Symbol <math>X \in N \cup \Sigma</math> je **nepoužitelný** v CFG <math>G = (N, \Sigma, P, S)</math> právě když v <math>G</math> neexistuje derivace tvaru <math>S \Rightarrow^\ast wXy \Rightarrow^\ast wxy</math> pro nějaká <math>w,x,y \in \Sigma^\ast</math>.
Řekneme, že <math>G</math> je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly.
</box>

**Nepoužitelnost typu I.:** Neexistuje terminální řetěz <math>w</math> takový, že <math>A \Rightarrow^\ast w</math>.
**Nepoužitelnost typu II.:** Neexistují řetězy <math>x,y</math> takové, že <math>S \Rightarrow^\ast xAy</math>.

<box 95% green round|Definice 3.13>Řekneme, že CFG <math>G = (N, \Sigma, P, S)</math> je bez <math>\epsilon</math>-pravidel právě když buď
  - <math>P</math> neobsahuje žádné <math>\epsilon</math>-pravidlo (tj. pravidlo tvaru <math>A \rightarrow \epsilon</math>) nebo 
  - v <math>P</math> existuje právě jedno <math>\epsilon</math>-pravidlo <math>S \rightarrow \epsilon</math> a <math>S</math> se nevyskytuje na pravé straně žádného pravidla z <math>P</math>.
</box>

**Jednoduchým pravidlem** nazýváme každé pravidlo tvaru <math>A \rightarrow B</math>, kde <math>A,B \in N</math>.

<box 95% green round|Definice 3.17 a Věta 3.18>CFG <math>G = (N, \Sigma, P, S)</math> se nazývá **necyklická**, právě když neexistuje <math>A \in N</math> takový, že <math>A \Rightarrow^+ A</math>.
\\
<math>G</math> se nazývá **vlastní**, právě když je bez nepoužitelných symbolů, bez <math>\epsilon</math>-pravidel a necyklická.
\\
Ke každému neprázdnému bezkontextovému jazyku existuje **vlastní** bezkontextová gramatika, která jej generuje.
</box>

<box 95% green round|Definice 3.28>Neterminál A v CFG <math>G = (N, \Sigma, P, S)</math> se nazývá **rekursivní** jestliže v <math>G</math> existuje derivace <math>A \Rightarrow^+ \alpha A\beta</math>. Je-li <math>\alpha = \epsilon</math> resp. <math>\beta = \epsilon</math>, pak A se nazývá levorekursivní resp. pravorekursivní. CFG bez levorekursivních terminálů se nazývá nelevorekursivní. <math>\alpha , \beta</math> jsou levé strany pravidel v //**P**//.
</box>


<note>
Osobně se domnívám, že otázka je dostatečně obsáhlá na to, aby při ní //nebyla// vyžadována znalost algoritmů na odstranění nepoužitelných symbolů, jednoduchých pravidel, levé rekurze atd. Pokud by někdo přeci jen chtěl tyto algoritmy nastudovat, nalezne je ve skriptech Formální jazyky a automaty, počínaje stranou 62 (=68 v pdf).
</note>



===== Normální formy bezkontextových gramatik =====
==== Chomského normální forma ====
<box 95% green round|Definice 3.19>Bezkontextová gramatika <math>G = (N, \Sigma, P, S)</math> je v Chomského normální formě (CNF) <math>\Leftrightarrow\ G</math> je bez <math>\epsilon</math>-pravidel (dle def. 3.13) a každé pravidlo z <math>P</math> má jeden z těchto tvarů:
  - <math>A \rightarrow BC,\ B,C\in N</math>
  - <math>A \rightarrow a,\ a \in \Sigma</math>
</box>

Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Chomského normální formě. Algoritmus transformace do CNF lze nalézt ve skriptech Automaty a gramatiky, strana 67. Ve zkratce algoritmus funguje tak, že pravé strany délky větší než 2 nahradí novými neterminály, a tak se tato pravá strana zkrátí. Například pravidlo X -> ABC se změní na pravidla X -> A<BC>, <BC> -> BC (<BC> je nový neterminál). Pro pravé strany délky 2, které se skládají z terminálu a neterminálu nahradí terminál novým neterminálem. Např. X -> aC se změní na X -> <a>C, <a> -> a.

==== Greibachové normální forma ====
<box 95% green round|Definice 3.33>Bezkontextová gramatika <math>G = (N, \Sigma, P, S)</math> je v Greibachové normální formě (GNF) právě když:
  * <math>G</math> je bez <math>\epsilon</math>-pravidel (dle def. 3.13)
  * každé pravidlo z <math>P</math> je tvaru <math>A \rightarrow a\alpha</math>, kde <math>a \in \Sigma</math> a <math>\alpha \in N^\ast</math>
</box>

Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě. Velmi zhruba naznačený postup je následující: Pokud je <math>L(G)</math> prázdný, pak jej definujeme jako jediné pravidlo (<math>S\rightarrow aS</math>). Pokud je <math>L(G)</math> neprázdný, odstraníme levou rekurzi a převedeme do GNF. Algoritmus transformace do GNF lze nalézt ve skriptech Automaty a gramatiky, strana 73,74.

===== Použití lemmatu o vkládání pro bezkontextové jazyky =====
<box 95% round green|Věta 3.24>Nechť L je CFL. Pak existují přirozená čísla <math>p,q</math> (závisející na L) taková, že každé slovo <math>z\in L</math>, <math>|z|>p</math> lze psát ve tvaru <math>z=uvwxy</math>, kde alespoň jedno ze slov <math>v,x</math> je neprázdné (tj. <math>vx \neq \epsilon</math> ), <math>|vwx| \le q</math> a <math>uv^i wx^iy \in L</math> pro všechna <math>i \ge 0</math>.
</box>
Pokud by to někdo chtěl čistě matematicky pro "lehčí" zapamatování:
<math>L \in CFL \Rightarrow \exists p,q \in N.</math>

<math>\forall z\in L.\ |z|>p.</math>

<math>\exists u,v,w,x,y \in \Sigma*.\ z=uvwxy\ \wedge</math>

<math>vx\neq \epsilon\ \wedge</math>

<math>|vwx| \leq q.</math>

<math>\forall i\geq 0 :\ uv^iwx^iy\in L</math>

Lemma o vkládání je vlastně ve tvaru implikace. Její kontrapositivní formu lze použít k důkazu, že nějaký jazyk //není// CFL. Stačí ukázat platnost následujícího tvrzení:

Pro libovolnou konstantu <math>n</math> existuje slovo <math>z</math>, <math>|z|>n</math> takové, že pro všechna slova <math>u</math>, <math>v</math>, <math>w</math>, <math>x</math>, <math>y</math> splňující: <math>z = uvwxy</math>, <math>vx \neq \epsilon</math> a <math>|vwx| \le n</math> existuje takové <math>i</math>, že <math>uv^i wx^i y \notin L</math>.

<box 95% round blue|Příklad><math>L=\{ wcw \, \mid\, w \in \{a,b \}*\}</math>

Pro libovolnou konstantu <math>n</math> existuje slovo <math>z \in L , |z| > n</math>: Zvolíme slovo <math>z</math> jako libovolné, pro důkaz vhodné, slovo <math>z</math> z jazyka <math>L</math> - <math>z = a^n b^n c a^n b^n</math>. Dále pro každé libovolné rozdělení slova <math>z</math> splňující následující podmínky: <math>z = uvwxy,\ vx \neq \epsilon,\ |vwx| \le n</math> musí existovat <math>i \in N_0</math> takové, že <math>uv^i wx^iy \notin L</math>.

Nyní musíme takové <math>i</math> nalézt. Položme tedy <math>i=0</math> a ověříme, že <math>uwy \notin L</math> rozebráním jednotlivých případů:

  - <math>c</math> není podslovo <math>vwx</math>. Potom ale <math>uwy = z' ca^n b^n</math> nebo <math>uwy = a^n b^n c z' </math>, kde <math>|z'| < 2n</math>. Z toho plyne, že <math>uwy \notin L</math>.
  - <math>c</math> je podslovo <math>vwx</math>. Tuto situaci rozdělíme ještě na další dva případy:
    * <math>c</math> je podslovo <math>vx</math>: Pak ale <math>c \notin uwy</math>, z čehož plyne, že <math>uwy \notin L</math> 
    * <math>c</math> je podslovo <math>w</math>: <math>|vwx| \leq n,\ uwy = a^n b^{n-|v|} c a^{n-|x|} b^n</math>. Současně <math>vx \neq \epsilon</math> a tudíž <math>|v|+|x| > 0</math> a tedy <math>uwy \notin L</math>.  
</box>

===== Uzávěrové vlastnosti bezkontextových jazyků =====

Třída bezkontextových jazyků **je** uzavřena vzhledem k operacím:
  * sjednocení
  * zřetězení
  * iterace
  * pozitivní iterace
  * průnik s regulárním jazykem
 
Třída bezkontextových jazyků **není** uzavřena vzhledem k operacím:
  * průnik
  * doplněk

Pro následující případy uvažujme:
<math>L_1</math> je generován CFG <math>G_1 = (N_1,\Sigma_1, P_1, S_1)</math>, <math>L_2</math> je  generován CFG <math>G_2 = (N_2,\Sigma_2, P_2, S_2)</math> a bez újmy na obecnosti budeme předpokládat <math>N_1 \cap N_2 = \emptyset</math>.

==== Sjednocení ====

Definujme <math>G = (N_1 \cup N_2 \cup \{S\},\,\Sigma_1 \cup \Sigma_2,\, P,\, S)</math>, kde <math>S</math> je nový symbol a <math>P = P_1 \cup P_2 \cup \{ S\rightarrow S_1,\, S\rightarrow S_2\}</math>

Jazyk <math>L = L_1 \cup L_2</math> je generován gramatikou <math>G</math>.


==== Zřetězení ====

Definujme <math>G = (N_1 \cup N_2 \cup \{S\},\,\Sigma_1 \cup \Sigma_2,\, P,\, S)</math>, kde <math>S</math> je nový symbol a <math>P = P_1 \cup P_2 \cup \{ S\rightarrow S_1S_2\}</math>

Jazyk <math>L = L_1 . L_2</math> je generován gramatikou <math>G</math>.

==== Iterace a pozitivní iterace ====

Definujme <math>G = (N_1 \cup \{S\},\,\Sigma_1,\, P,\, S)</math>, kde <math>S</math> je nový symbol a <math>P = P_1 \cup \{ S\rightarrow SS_1|\epsilon \}</math>

Jazyk <math>L = L_1^{\ast}</math> je generován gramatikou <math>G</math>.

Definujme <math>G = (N_1 \cup \{S\},\,\Sigma_1,\, P,\, S)</math>, kde <math>S</math> je nový symbol a <math>P = P_1 \cup \{ S\rightarrow SS_1|S_1 \}</math>

Jazyk <math>L = L_1^{+}</math> je generován gramatikou <math>G</math>.

==== Průnik a doplněk ====
<math>L_1 = \{ a^n b^n c^m\, \mid\, m,n \ge 1\},\ L_2 = \{ a^m b^n c^m\, \mid\, m,n \ge 1\}</math>

Kdyby byla třída bezkontextových jazyků uzavřena vzhledem k operaci průnik, pak i <math>L_1 \cap L_2 = \{ a^n b^n c^n \, \mid \, n \ge 1 \}</math> by musel být bezkontextový, což však není.

Neuzavřenost vůči doplňku plyne z uzavřenosti třídy bezkontextových jazyků vzhledem k operaci sjednocení, neuzavřenosti na průnik a De Morganových pravidel:

<math>L_1 \cap L_2 = \neg(\neg L_1 \cup \neg L_2)</math>

===== Rozhodnutelné vlastnosti =====
 Pro třídu bezkontextových jazyků jsou rozhodnutelné následující vlastnosti:
  * **Problém příslušnosti:** Ke každé CFG je možné sestrojit PDA a můžeme tak ověřit jestli daný PDA přijme nebo zamítne slovo //w//.
  * **Problém prázdnosti:** Stačí ověřit zda <math>S \in N_e</math>. (<math>N_e</math> je množina použitelných symbolů vzhledem k typu I.)
  * **Problém konečnosti:** Ke každé CFG lze sestrojit čísla <math>m,n</math> taková, že <math>L(G)</math> je nekonečný, právě když existuje slovo <math>z \in L(G)</math> takové, že <math>m<|z|<n</math> ((Důkaz je uveden ve skriptech Formální jazyky a automaty I., strana 96)).

===== Poznámka =====
Lingvista Noam Chomsky rozdělil gramatiky do čtyř skupin (typů) na základě různých omezení na tvar pravidel a  podle jejich popisné síly. 

Chomského hierarchie rozlišuje tyto čtyři (základní) typy gramatik - viz [[home:inf:ap8#poznamka|Regulární jazyky - poznámka]]

===== Předměty =====
[[https://is.muni.cz/auth/predmety/predmet.pl?id=427603|FI:IB005]] Formální jazyky a automaty I prof. RNDr. Mojmír Křetínský, CSc.
[[https://is.muni.cz/auth/predmety/predmet.pl?id=454974|FI:IB102]] Automaty a gramatiky RNDr. Jan Strejček, Ph.D.

===== Zdroje =====
[[http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf|Skripta k IB005]]
[[http://www.fi.muni.cz/usr/kretinsky/fja1.html|Stránky prof. Křetínský]]
[[http://www.fi.muni.cz/~xstrejc/IB102/|Stránky Strejček]]


===== Vypracoval =====
Honza Palas, hotovo

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/bezkontextove_jazyky.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~