====== N-AP14 ======
====== Zadání ======
Bezkontextové jazyky. Bezkontextové gramatiky. Zásobníkové automaty. Normální formy bezkontextových gramatik. Převod bezkontextové gramatiky na zásobníkové automaty. Použití pumping lemmatu a uzávěrových vlastností bezkontextových jazyků.

====== Bezkontextové jazyky ======

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í.)) 

<box 90% round blue|Definice>**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
</box> 


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>).

===== 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




====== Zásobníkový automat ======
Na vstupní pásce je napsáno slovo (nad jistou vstupní abecedou) – lze z ní pouze číst, čtecí hlava se pohybuje pouze vpravo. Automat může na vrchol zásobníku ukládat symboly (z jisté abecedy) a ty následně číst – čte vždy jen vrchol zásobníku, přečtený symbol je odstraněn = systém LIFO (Last In First Out).


<box 95% blue round|Definice 3.36. - PDA ((skripta Automaty a formální jazyky I, str. 77))>**Nedeterministický zásobníkový automat** (PushDown Automaton, PDA) je sedmice  <math>M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F)</math>, kde
• <math>Q</math> je konečná množina, jejíž prvky nazýváme stavy,
• <math>\Sigma</math> je konečná množina, tzv. vstupní abeceda,
• <math>\Gamma</math> je konečná množina, tzv. zásobníková abeceda,
• <math>\delta : (Q \times (\Sigma \cup{{\varepsilon}})\times \Gamma) \rightarrow P_{Fin}(Q \times \Gamma^{*})</math>, tzv. (parciální) přechodová funkce (zápis <math>P_{Fin}(Q \times \Gamma^{*})</math> značí množinu všech konečných podmnožin množiny <math>Q\times \Gamma^{*}</math> -- dvojice stav a řetězec symbolů zásobníkové abecedy),
• <math>q_{0} \in Q</math> je počáteční stav,
• <math>Z_{0} \in \Gamma</math> je počáteční symbol v zásobníku,
• <math>F \subseteq Q</math> je množina koncových stavů.
</box>

<math>\delta(q_{0}, a, Z_{0}) = \{(q_{0}, AZ_{0})\}; Z_{0}</math> ... dno zásobníku, A ... vrchol zásobníku, přidal se v tomto kroku
<math>\delta(q_{0}, c,  A) = \{(q_{1}, A)\}</math> ... obsah zásobníku se nezměnil, pouze se přešlo do stavu q<sub>1</sub>
<math>\delta(q_{1}, b, A) = \{(q_{1}, \varepsilon)\}</math> ... stav se nezměnil, ze zásobníku se přečetlo A -- bylo odebráno
**<color blue>vrchol zásobníku běžného PDA se píše vlevo</color>**

<note >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>

===== Výpočet zásobníkového automatu =====


<box 95% round blue|Definice 3.37. Konfigurace, krok výpočtu ((skripta Automaty a formální jazyky I, str. 78))>Nechť <math>M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F)</math> je PDA.
**Konfigurací** nazveme libovolný prvek <math>(p, w, \alpha) \in Q \times \Sigma^{*} \times \Gamma^{*}</math>.
Na množině všech konfigurací automatu M definujeme binární relaci **krok výpočtu** <math>|\frac{\ \ \ }{\ M \ }</math> takto:
<math>(p, aw, Z \alpha) |\frac{\ \ \ }{\ M \ }(q, w, \gamma \alpha) \Leftrightarrow^{def} \exists(q, \gamma) \in  \delta (p, a, Z)</math> pro <math>a \in \Sigma \cup \lbrace \varepsilon \rbrace</math>

Reflexivní a tranzitivní uzávěr relace <math>|\frac{\ \ \ }{\ M \ }</math> značíme <math>|\frac{\ * \ }{\ M \ }</math>.
Je-li M zřejmý z kontextu, píšeme pouze <math>|\frac{\ \ \ }{\ \ \ }</math> resp. <math>|\frac{\ * \ }{\ \ \ }</math>.</box>

===== Akceptující výpočet PDA =====


<box 95% round blue|Definice 3.37. (pokračování) -  akceptování ((skripta Automaty a formální jazyky I, str. 78))>**Jazyk akceptovaný** PDA M **koncovým stavem** definujeme jako
<math>L(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q_{f}, \varepsilon, \alpha)</math>, kde <math>q_{f} \in  F, \alpha \in \Gamma^{*} \rbrace</math>

a jazyk akceptovaný PDA M **prázdným zásobníkem** definujeme
<math>L_{e}(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q, \varepsilon, \varepsilon)</math>, kde <math>q \in Q \rbrace</math>.</box>

Takto definovaný PDA je nedeterministický -- akceptuje slovo, jestliže existuje **alespoň jeden výpočet**, který vede z počáteční konfigurace do akceptující. V případě možnosti automat "hádá správně".

==== Ekvivalence dvou způsobů akceptování ====


Pro každý jazyk L platí:
<box 95%  round green| Věta 3.39, ((skripta Automaty a formální jazyky I, str. 78))><math>L = L(N)</math> pro nějaký PDA N <math>\Leftrightarrow  L = L_{e}(M)</math> pro nějaký PDA M.</box>
PDA **N** akceptuje koncovým stavem, PDA **M** prázdným zásobníkem
=== koncový stav => prázdná paměť ===
**Intuice:**
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
• pokračovat v simulaci automatu N nebo
• přejít do nově přidaného stavu <math>q_{\varepsilon}</math>, v němž vyprázdní zásobník.
**Komplikace:**
Automat N by vyprázdnil zásobník, aniž by došel do koncového stavu -- akceptoval by i nežádoucí vstup.
**Řešení:**
Před zahájením simulace bude u M na dně zásovníku nový symbol, který nedovolíme odstranit jinde, než ve stavu <math>q_{\varepsilon}</math>.

=== prázdná paměť => koncový stav ===

K danému M zkonstruujeme N simulující jeho činnost.
• N si před simulací přidá na dno zásobníku nový symbol.
• Je-li N schopen číst tento symbol (tj. zásobník automatu M je prázdný), potom N přejde do nově přidaného stavu <math>q_{f}</math>, který je koncovým stavem.

důkaz viz skripta (( skripta Automaty a formální jazyky I, str. 78)), konstrukce viz slidy (([[http://www.fi.muni.cz/~xstrejc/IB102/|Web IB102]] - slajdy10, str. 5 a 8))

===== Grafická reprezentace konfigurací =====


  * Zpravidla nekonečné
  * **Vnitřní konfigurace** (= částečná konfigurace) = aktuální stav a celý obsah zásobníku (vrchol se píše vlevo)

**Příklad:**
PDA <math> A = (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \{r\})</math> - akceptuje koncovým stavem
PDA <math>A'= (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \emptyset)</math> - akceptuje prázdným zásobníkem

Přechodovou funkci mají oba automaty stejnou:
<math>\delta(q, a, Z) = \{(q, AZ)\}</math>
<math>\delta(q, a, A) = \{(q, AA)\}</math>
<math>\delta(q, c, Z) = \{(r, Z)\}</math>
<math>\delta(q, c, A) = \{(r, A)\}</math>
<math>\delta(r, b, Z) = \{(r, \epsilon)\}</math>
<math>\delta(r, b, A) = \{(r, \epsilon)\} </math>

Grafické znázornění obou automatů, žlutě vybarvené jsou konfigurace, ve kterých akceptuje automat A, v tlustě orámované konfiguraci akceptuje automat A'
{{:home:inf:pda_graficky.png|}}


====== Normální formy bezkontextových gramatik ======

===== Chomského normální forma =====

<box 95% blue 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% blue 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.

====== Převod bezkontextové gramatiky na zásobníkové automaty ======
<box 95% round green|Věta 3.51 ((skripta Formální jazyky a automaty I, str. 86))>Ke každému PDA M lze sestrojit CFG G takovou, že <math>L_{e}(M) = L(G)</math>.</box>Jednoduchý algoritmus na prvnim slidu http://www.nvc.cs.vt.edu/~jzhang/cs5104/Note-8.pdf
priklad si bud vygooglovat nebo strana 89 ve skriptech FJA
<box 95% round green|Věta 3.47 ((skripta Formální jazyky a automaty I, str. 83))>Ke každé CFG G lze sestrojit PDA M takový, že <math>L(G) = L_{e}(M)</math>.</box>Strana 25, 26 http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/PDA.pdf
<box 95% round green|Důsledek 3.52 ((skripta Formální jazyky a automaty I, str. 89))>Třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.</box>Konstrukce PDA řeší problém syntaktické analýzy. (platí pro dané G a w: <math>w \in L(G)?</math>)
<math>w \in L(G) \Leftrightarrow</math> v G existuje derivační strom s výsledkem w.

== Nedeterministická syntaktická analýza shora dolů ==
Budování derivačního stromu simuluje levé derivace, tj. vždy rozvíjíme nejlevější neterminál.<box 95% round green|Důsledek 3.47 ((skripta Formální jazyky a automaty I, str. 83))>Ke každé CFG G lze sestrojit PDA M takový, že <math>L(G) = L_{e}(M)</math>.</box>**Důkaz.** K dané gramatice G konstruujeme PDA M, který simuluje levé derivace v G (rozvíjíme nejlevější neterminál).
  * V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou <math>X_{1} ...X_{n}</math> nějakého A-pravidla.
  * V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem <math>X_{1} ...X_{n}</math>.
<math>M = (\lbrace q \rbrace, \Sigma,N \cup \Sigma, \delta, q, S, \emptyset)</math>, kde <math>\delta</math> je definována:
  * <math>\delta(q, \varepsilon, A)</math> obsahuje <math>(q, \alpha)</math> právě když <math>A \rightarrow \alpha \in P</math>
  * <math>\delta(q, a, a) = \lbrace(q, \varepsilon)\rbrace</math> pro všechna <math>a \in \Sigma</math>

korektnost + důkaz viz skripta ((str. 84 skripta Formální jazyky a automaty I, slajdy11 - str. 12))

== Nedeterministická syntaktická analýza zdola nahoru ==
<box 95% round green|Lemma 3.55 ((skripta Formální jazyky a automaty I, str. 90))>Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R takový, že L(G) = L(R).</box>**Důkaz.** 
**<color blue>Vrchol zásobníku píšeme vpravo.</color>**
Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G v obráceném pořadí.
PDA R má kroky dvojího typu:
  - může kdykoli číst do zásobníku vstupní symbol,
  - **(redukce)** je-li na vrcholu zásobníku řetěz tvořící pravou stranu nějakého pravidla v G, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte).

Nechť <math>G = (N, \Sigma, P, S)</math>.
Položme <math>R = (\lbrace q, r \rbrace, \Sigma, N \cup \Sigma \cup \lbrace \bot \rbrace, \delta, q, \bot, \lbrace r \rbrace )</math>, kde <math>\bot</math> je nově přidaný symbol a kde <math>\delta</math> je definována takto:
  - <math>\delta(q, a, \varepsilon) = \lbrace(q, a)\rbrace</math> pro všechna <math>a \in \Sigma</math> //...načítání vstupu na zásobník//,
  - je-li <math>A \rightarrow \alpha</math>, pak <math>\delta(q, \varepsilon, \alpha)</math> obsahuje (q, A) //...redukce//,
  - <math>\delta(q, \varepsilon, \bot S) = \lbrace(r, \varepsilon)\rbrace</math> //...akceptování//.
korektnost viz slajdy ((slajdy11, str. 17))

== Příklad: ==
Zadání: 
G = ({S, A, B}, {a, b}, P, S)
P = 
{S -> <math>\varepsilon</math> | abSA
 A -> AaB | aB | a,
 B -> aSS | bA | <math>\varepsilon</math>}
Derivační strom pro slovo w = abababaa
{{:home:inf:pda_analyza.png}}
**Automat, který provádí syntaktickou analýzu shora dolů:**
A = ({q}, {a,b}, {S, A, B, a, b}, <math>\delta</math>, q, S, <math>\emptyset</math>)
2 typy přechodových fcí:
  * //levou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA,    pravou stranu pravidel z gram. na zásobník pravé strany//
<math>\delta</math>(q, <math>\varepsilon</math>, S) = {(q, <math>\varepsilon</math>), (q, abSA)}
<math>\delta</math>(q, <math>\varepsilon</math>, A) = {(q, AaB), (q, aB), (q, a)}
<math>\delta</math>(q, <math>\varepsilon</math>, B) = { (q, aSS), (q, bA), (q, <math>\varepsilon</math>)}
  * //"mazací" přechodové fce//
<math>\delta</math>(q, a, a) = {(q, <math>\varepsilon</math>)}
<math>\delta</math>(q, b, b) = {(q, <math>\varepsilon</math>)}

  * **Akceptující výpočet nad slovem abababaa:**
(intuice: postupuju podle derivačního stromu, sleduju jeho rozvíjení odshora a čtu ho zleva)
**<color red>vrchol zásobníku je vlevo</color>**
<math>(q, abababaa, S) |\frac{\ \ \ }{\ \ \ } (q, abababaa, abSA) |\frac{\ \ \ }{\ \ \ } (q, bababaa, bSA) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math>(q, ababaa, SA) |\frac{\ \ \ }{\ \ \ } (q, ababaa, A) |\frac{\ \ \ }{\ \ \ } (q, ababaa, AaB) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math> (q, ababaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, BaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, bAaB) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math> (q, abaa, AaB) |\frac{\ \ \ }{\ \ \ } (q, abaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, baa, BaB) |\frac{\ \ \ }{\ \ \ }</math>\\ 
 <math> (q, baa, bAaB) |\frac{\ \ \ }{\ \ \ } (q, aa, AaB) |\frac{\ \ \ }{\ \ \ } (q, aa, aaB) |\frac{\ \ \ }{\ \ \ } </math>\\ 
 <math>(q, a, aB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, B) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \varepsilon)</math>
... celé slovo se přečetlo a zásobník se vyprázdnil <math>\rightarrow</math> **automat slovo akceptuje**

**Automat pro syntaktickou analýzu zdola nahoru:**
<math>A_{2} = (\{q, r\}, \{ a,b\} , \{S, A, B, a, b, \bot\}, \delta, q, \bot, \{ r\})</math>
3 typy přechodových funkcí:
  * //terminály z gramatiky se předávají na zásobník//
<math>\delta</math>(q, a, <math>\varepsilon</math>) = {(q, a)}
<math>\delta</math>(q, b, <math>\varepsilon</math>) = {(q, b)}
  * //pravou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA,    levou stranu pravidel z gram. na zásobník pravé strany//
<math>\delta</math>(q, <math>\varepsilon</math>, abSA) = {(q, S)}
<math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, S), (q, B)} **<color red>! ! !</color>** Nesmí být rozděleno na: <math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, S)} a <math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, B)}, nebyla by to pak funkce.
<math>\delta</math>(q, <math>\varepsilon</math>, AaB) = <math>\delta</math>(q, <math>\varepsilon</math>, aB) = <math>\delta</math>(q, <math>\varepsilon</math>, a) = {(q, A)}
<math>\delta</math>(q, <math>\varepsilon</math>, aSS) = <math>\delta</math>(q, <math>\varepsilon</math>, bA) = {(q, B)}
  * //přechod do koncového stavu//
<math>\delta</math>(q, <math>\varepsilon</math>,  <math>\bot</math>S) = {(r, <math>\varepsilon</math>)}


  * **Akceptující výpočet nad slovem abababaa:**
(Intuice: čtu derivační strom zleva -- jako když teče voda (= používám první skupinu pravidel), pokud by voda musela téct do kopce, použiju pravidlo z druhé skupiny)
**<color red>vrchol zásobníku je vpravo</color>**
<math>(q, abababaa, \bot) |\frac{\ \ \ }{\ \ \ } (q, bababaa, \bot a) |\frac{\ \ \ }{\ \ \ } (q, ababaa, \bot ab) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, ababaa, \bot abS) |\frac{\ \ \ }{\ \ \ } (q, babaa, \bot abSa) |\frac{\ \ \ }{\ \ \ } (q, abaa, \bot abSab) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, baa, \bot abSaba) |\frac{\ \ \ }{\ \ \ } (q, aa, \bot abSabab) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSababa) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, a, \bot abSababA) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabA) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, a, \bot abSaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSAa) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, \varepsilon, \bot abSAaB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot S) |\frac{\ \ \ }{\ \ \ } (r, \varepsilon, \varepsilon)</math>
... automat přečetl celé slovo a přešel do koncového stavu r, **slovo akceptuje**.

U nedeterministické analýzy automat slovo neakceptuje, pokud **žádný** z možných výpočtů není akceptující.

====== Použití pumping lemmatu a uzávěrových vlastností bezkontextových jazyků ======
===== 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>, délky alespoň <math>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>
Explicitněji lze lemma přepsat takto:
Za předpokladu, že <math>L \in CFL</math>, pak 
<math>\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 vx\neq \epsilon\ \wedge|vwx| \leq q.</math>

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

Lemma o vkládání je ve tvaru implikace P ⇒ Q, kde P je výrok, že L je CFL a Q jsou uvedené vlastnosti. Této implikace (resp. 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>

====== Předměty ======



====== Vypracoval ======


Marek Menšík UČO 255679 
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů.


====== Použitá literatura a weby ======


~~DISCUSSION~~