====== N-AP13 ======

====== Zadání ======

Regulární jazyky. Konečné automaty, regulární gramatiky a regulární výrazy. Minimalizace konečného automatu. Převod nedeterministického konečného automatu na deterministický automat. Vztah mezi konečnými automaty a regulárními jazyky. Použití pumping lemmatu pro regulární jazyky.





===== Regulární jazyky =====



**Abeceda** je libovolná konečná množina, jejíž prvky se nazývají znaky. Abeceda může být i prázdná množina, zapisuje se Σ.
**Slovo** je libovolná konečná posloupnost znaků z abecedy. 
**Jazykem** se rozumí libovolná množina slov nad nějakou abecedou. Jazyky mohou být konečné i nekonečné.
**Regulární jazyk** je jazyk generovatelný regulární gramatikou. Též je to jazyk rozpoznatelný konečným automatem nebo popsaný regulárním výrazem.

==== Vlastnosti regulárních jazyků ====

Popis vlastností regulárních jazyků je důležitý pro popis regulárních výrazů.
  * Ø je regulární jazyk.
  * { ε } je regulární jazyk.
  * { a } je regulární jazyk.



Pokud jsou A a B regulární jazyky, pak **sjednocení, průnik, rozdíl, zřetězení** a **iterace** jsou regulární jazyky.
Pokud je A regulární jazyk, pak **komplement** A je regulární jazyk.
Pokud je A regulární jazyk, pak **zrcadlový obraz** jazyka A je regulární jazyk.
Všechny konečné jazyky jsou regulární.
**Příklad**: Iterace jazyka {"ab", "c"}*  je { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }


**Jazyk** //L// je **regulární**, právě když:
  * může být vygenerován **regulární gramatikou** (tzn. existuje regulární gramatika //G// taková, že //L(G) = L//),
  *je akceptovaný nějakým **deterministickým konečným automatem** (tzn. existuje deterministický konečný automat //M// takový, že //L(M) = L//),
  * je akceptovaný nějakým **nedeterministickým konečným automatem** (tzn. existuje nedeterministický konečný automat //M// takový, že //L(M) = L//),
  * může být popsán **regulárním výrazem** (tzn. existuje regulární výraz //RE// takový, že //L(RE) = L//)

==== Uzávěrové vlastnosti regulárních jazyků ====

Třída regulárních jazyků je uzavřena na:
  * **sjednocení** (//L<sub>1</sub>// <m>union</m> //L<sub>2</sub>//),
  * **průnik** (//L<sub>1</sub>// <m>inter</m> //L<sub>2</sub>//),
  * **rozdíl** (//L<sub>1</sub>// \ //L<sub>2</sub>//),
  * **komplement** (co--//L//),
  * **zřetězení** (//L<sub>1</sub>//.//L<sub>2</sub>//)
  * **iteraci** (//L//*),
  * **pozitivní iteraci** (//L//<sup>+</sup>),
  * **zrcadlový obraz (reverzi)** (//L<sup>R</sup>//)

===== Konečné automaty =====
<box 90% round blue|Definice 2.1. ((viz skripta Automaty a formální jazyky I, str. 11))>**Konečný automat** //M// je pětice (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//), kde
  * //Q// je neprázdná konečná množina **stavů**,
  * <m>Sigma</m> je konečná množina **vstupních symbolů** (vstupní abeceda),
  * <m>delta</m>: //Q x //<m>Sigma</m> //-> Q// je parciální **přechodová funkce** (<m>delta</m>: //Q x //<m>Sigma</m>// -> 2<sup>Q</sup>// totální v případě nedeterministického konečného automatu),
  * //q<sub>0</sub>// <m>in</m> //Q// je **počáteční stav**,
  * //F// <m>⊆</m> //Q// je množina **koncových stavů**
</box>
**Slovo akceptované** automatem M je právě takové slovo, pod kterým automat přejde z počátečního stavu do koncového stavu.
**Jazyk akceptovaný** automatem M je množina všech slov, na kterých automat přejde z počátečního stavu do koncového stavu. 
=== Rozšířená přechodová funkce deterministického konečného automatu: ===
Abychom mohli definovat jazyk akceptovaný automatem, je třeba zavést rozšířenou přechodovou funkci 

<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> Q// definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = //q// pro každý stav //q// <m>in</m> //Q//
  * <m>hat{delta}</m>(//q//, //wa//) = 
    *<m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) je-li <m>hat{delta}</m>(//q//, //w//) i <m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) definováno
    *<m>ortho</m> jinak

Jazyk akceptovaný konečným automatem //M//, označovaný //L//(//M//) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
//L//(//M//) = {//w// <m>in Sigma</m>* | <m>hat{delta}</m>(//q<sub>0</sub>//,//w//) <m>in</m> //F//}

=== Rozšířená přechodová funkce nedeterministického konečného automatu: ===
<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> 2<sup>Q</sup>//, definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = {q}
  * <m>hat{delta}</m>(//q//, //wa//) = <m>bigcup{p in hat{delta}(q,w)}{}{delta(p,a)}</m>

Jazyk akceptovaný nedeterministickým konečným automatem //M//, označovaný //L//(//M//) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
//L//(//M//) = {//w// <m>in Sigma</m>* | <m>hat{delta}</m>(//q<sub>0</sub>//,//w//) <m>inter</m> //F// <m>!= varnothing</m>}


===== Regulární gramatiky =====

<box 90% round blue|Definice 1.2. ((viz skripta Automaty a formální jazyky I, str. 4))>**Gramatika** //G// je čtveřice (//N//, <m>Sigma</m>, //P//, //S//), kde
  * //N// je neprázdná konečná množina neterminálních symbolů (**neterminálů**),
  * <m>Sigma</m> je konečná množina terminálních symbolů (**terminálů**) taková, že <m>N inter Sigma = varnothing</m>; <m>N union Sigma = V</m> je množina **všech symbolů** gramatiky,
  * //P// <m>⊆</m> //V*NV* x V*// je konečná množina **pravidel**. Pravidlo <m>(alpha, beta)</m> obvykle zapisujeme ve tvaru  <m>alpha right beta</m> (čteme "alfa přepiš na beta"),
  * //S// <m>in</m> //N// je **počáteční** neterminál, neboli kořen gramatiky.
</box> 

**Gramatika** je **regulární**, jestliže každé její pravidlo je tvaru //A -> aB// (nebo //A → Aa//, tzv. levo lineární gramatika) nebo //A -> a// s výjimkou //S -> //<m>epsilon</m>, pokud se //S// nevyskytuje na pravé straně žádného pravidla. 
Je to gramatika typu 3 podle //Chomského hierarchie gramatik//.

===== Regulární výrazy =====
Množina **regulárních výrazů** nad abecedou <m>Sigma</m>, označovaná //RE//(<m>Sigma</m>), je definována induktivně takto:
  - <m>epsilon</m>, <m>varnothing</m> a //**a**// pro každé //a// <m>in</m> <m>Sigma</m> jsou (základní) regulární výrazy nad <m>Sigma</m>.
  - Jsou-li //E//, //F// regulární výrazy nad <m>Sigma</m>, jsou také (//E.F//), (//E// + //F//) a (//E*//) regulární výrazy nad <m>Sigma</m>.
  - Každý regulární výraz vznikne po konečném počtu aplikací kroků 1--2.

Závorky je možné vypouštět s tím, že největší prioritu má operátor " * ", pak " . " a nakonec " + "
Každý regulární výraz E nad abecedou <m>Sigma</m> popisuje jazyk //L(E)// nad abecedou <m>Sigma</m> podle těchto pravidel:
  * L(<m>epsilon</m>) = <m>{epsilon}</m>
  * L(<m>varnothing</m>) = <m>varnothing</m>
  * L(**a**) = {a} pro každé //a// <m>in</m> <m>Sigma</m>
  * L(E.F) = L(E).L(F)
  * L(E+F) = L(E) <m>union</m> L(F)
  * L(E*) = L(E)*
Regulární výrazy jsou tedy výrazy, které popisují množinu slov. Jsou ekvivalentní nějakému automatu případně gramatice. Využívají vlastností sjednoceni, průniku, rozdílu, iterace, zřetězení a komplementu. Lze napsat algoritmus, který rozhodne, zda jsou dva regulární výrazy ekvivalentní, tj. popisují stejný jazyk a redukovat daný jazyk na nějaký minimální automat.

Ekvivalenci mezi regulárními výrazy a konečnými automaty shrnuje **Kleeneho veta**:
<box 95% round green|Kleeneho věta>Libovolný jazyk je popsatelný regulárním výrazem, právě když je rozpoznatelný konečným automatem.</box>

===== Minimalizace konečného automatu =====

Minimální automat je automat s nejmenším počtem stavů, který rozpoznává daný regulární jazyk L. Lze jej sestrojit z jakéhokoliv automatu rozpoznávající nějaký jazyk L.
Existence minimálního konečného automatu souvisí s Myhill--Nerodovou větou (viz otázka [[home:inf:ap8|AP8,IN8 Regulární jazyky]]), kterou můžeme přeformulovat takto:
<box 90% round green|Věta 2.29 Myhill--Nerodova, 2. varianta((viz skripta Automaty a formální jazyky I, str. 26))>Počet stavů libovolného minimálního automatu rozpoznávajícího jazyk //L// je roven indexu prefixové ekvivalence //~<sub>L</sub>//. (Takový konečný automat existuje právě když index //~<sub>L</sub>// je konečný.)
</box>

<box 90% round| //Důsledek M-N věty//> Minimální konečný automat akceptující jazyk //L// je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).
</box>

Minimalizace konečného automatu probíhá tak, že nejprve jsou odstraněny **nedosažitelné** stavy a poté jsou ztotožněny **jazykově ekvivalentní** stavy.

==== Odstranění nedosažitelných stavů ====
<box 90% round blue| Definice - dosažitelné a nedosažitelné stavy>Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat. Stav //q// <m>in</m> //Q// nazveme **dosažitelný**, pokud existuje //w// <m>in Sigma</m>* takové, že <m>hat{delta}</m>(//q<sub>0</sub>//, //w//) = //q//. Stav je **nedosažitelný**, pokud není dosažitelný.
</box>

=== Algoritmus pro eliminaci nedosažitelných stavů konečného automatu ===

**Vstup**: Konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//)
**Výstup**: Ekvivalentní automat //M'// bez nedosažitelných stavů.

<box 90% | Algoritmus>//i// := 0
//S<sub>i</sub>// := {//q<sub>0</sub>//}
**repeat** //S//<sub>//i//+1</sub> := //S<sub>i</sub>// <m>union</m> {//q// | <m>exists</m>//p// <m>in</m> //S<sub>i</sub>//, //a// <m>in Sigma</m>: <m>delta</m>(//p//, //a//) = //q//}
//i// := //i// + 1
**until** //S<sub>i</sub>// = //S//<sub>//i//--1</sub>
//Q'// := //S<sub>i</sub>//
//M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>|<sub>//Q'//</sub>, //q<sub>0</sub>//, //F// <m>inter</m> //Q'//)
</box>

//Poznámka//: Zápis <m>delta</m>|<sub>//Q'//</sub> znamená, že funkce <m>delta</m> je omezena na množinu //Q'//.
//Intuitivně//: Množina //S<sub>i</sub>// je množina stavů dosažitelná v automatu v maximálně //i// krocích. 

==== Ztotožnění jazykově ekvivalentních stavů ====
Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat bez nedosažitelných stavů, jehož přechodová funkce je totální.
<box 90% round blue| Definice - jazykově ekvivalentní stavy>Stavy //p//, //q// nazveme **jazykově ekvivalentní**, psáno //p// ≡ //q//, pokud 
//p// ≡ //q// <m>doubleleftright forall</m>//w// <m>in Sigma</m>* : (<m>hat{delta}</m>(//p//, //w//) <m>in</m> //F// <m>doubleleftright hat{delta}</m>(//q//, //w//) <m>in</m> //F//).
</box>

<box 90% round blue| Definice - Redukt>**Reduktem** automatu //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) nazveme konečný automat //M///<sub>≡</sub> = (//Q///<sub>≡</sub>, <m>Sigma</m>, <m>eta</m>, [//q<sub>0</sub>//], //F///<sub>≡</sub>), kde:
  * Stavy jsou třídy rozkladu //Q///<sub>≡</sub> (třída obsahující stav //q// je [//q//]).
  * Přechodová funkce <m>eta</m> je funkce splňující:
<m>forall</m>//p//,//q// <m>in</m> //Q//, <m>forall</m>a <m>in Sigma</m>: <m>delta</m>(//q//, //a//) = //p// <m>doubleright eta</m>([//q//], //a//) = [//p//].
  * Počáteční stav je třída rozkladu //Q///<sub>≡</sub> obsahující stav //q<sub>0</sub>//.
  * Koncové stavy jsou právě ty třídy rozkladu //Q///<sub>≡</sub>, které obsahují alespoň jeden koncový stav.
</box>

<box 90% round green| Věta> Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat bez nedosažitelných stavů s totální přechodovou funkcí. Pak //L//(//M//) = //L//(//M///<sub>≡</sub>).
</box>

<box 90% round blue| Definice> Pro každé //i// <m>in bbN</m><sub>0</sub> definujeme binární relaci ≡<sub>//i//</sub> na //Q// předpisem
//p// ≡<sub>//i//</sub> //q// <m>doubleleftright forall</m>//w// <m>in Sigma</m>*.|//w//| <m><=</m> //i// : (<m>hat{delta}</m>(//p//, //w//) <m>in</m> //F// <m>doubleleftright hat{delta}</m>(//q//, //w//) <m>in</m> //F//)
  * //p// ≡<sub>//i//</sub> //q// právě když //p// a //q// nelze "rozlišit" žádným slovem délky <m><=</m> //i//
  * //p// ≡ //q// právě když //p// ≡<sub>//i//</sub> //q// pro každé //i// <m>in bbN</m><sub>0</sub>. (≡ = <m>bigcap{i=0}{infty}{≡}</m><sub>i</sub>)
  - ≡<sub>0</sub> = {(//p//, //q//) | //p// <m>in</m> //F// <m>doubleleftright</m> //q// <m>in</m> //F//}
  - ≡<sub>//i//+1</sub> = {(//p//, //q//) | //p// ≡<sub>//i//</sub> //q// <m>wedge forall</m>//a// <m>in Sigma</m> : <m>delta</m>(//p//, //a//) ≡<sub>//i//</sub> <m>delta</m>(//q//, //a//)}
</box>

=== Algoritmus konstrukce minimálního automatu ===
**Vstup**: Konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) bez nedosažitelných stavů s totální přechodovou funkcí
**Výstup**: Redukt //M///<sub>≡</sub>.

<box 90% | Algoritmus>//i// := 0
≡<sub>0</sub> := {(//p//, //q//) | //p// <m>in</m> //F// <m>doubleleftright</m> //q// <m>in</m> //F//}
**repeat**
≡<sub>//i//+1</sub> := {(//p//, //q//) | //p// ≡<sub>//i//</sub> //q// <m>wedge forall</m>//a// <m>in Sigma</m> : <m>delta</m>(//p//, //a//) ≡<sub>//i//</sub> <m>delta</m>(//q//, //a//)}
//i// := //i// + 1
**until** ≡<sub>//i//</sub> = ≡<sub>//i//--1</sub>
≡ = ≡<sub>//i//</sub>
//M///<sub>≡</sub> := (//Q///<sub>≡</sub>, <m>Sigma</m>, <m>eta</m>, [//q<sub>0</sub>//], //F///<sub>≡</sub>)
</box>

== Příklad ==
{{:home:inf:automat_3min.jpg|Konstrukce minimálního automatu}}
  * První tabulka obsahuje nedostupné stavy (stav 7).
  * Druhá tabulka ukazuje přechodovou funkci po úpravě na totální, přidáním nového stavu N a nasměrováním všech nedefinovaných přechodů do něj.

  * Ostatní čtyři tabulky reprezentují postupnou minimalizaci automatu.
<box orange 100% round|Praktické vysvětlení algoritmu>Na začátku tabulku přechodové funkce rozdělíme do dvou částí(tříd), do druhé části zaznamenáme výstupní stavy, do první části ty ostatní. Obě části označíme římskými číslicemi. Postupně procházíme stavy automatu který chceme minimalizovat, a pro jednotlivé prvky abecedy zjišťujeme, ve které části tabulky se nachází stav do kterého se při přechodu dostaneme. Číslo této části zapíšeme do tabulky k prvku abecedy u zpracovávaného stavu. (**tabulka 3**)
\\
Tabulku opět rozdělíme, do částí(tříd) které označíme římskými číslicemi, v každé necháme stavy ze kterých se pod všemi prvky abecedy dostaneme do stejných částí tabulky. Aplikujeme předchozí krok.(**tabulka 4,5**)
\\
Tento postup aplikujeme dokud každá část tabulky neobsahuje jen stavy přecházející do stejných tříd. Ve výsledné tabulce nezapisujeme názvy stavů, ale jen označení tříd s jejich přechody(**tabulka 6**).
</box>

===== Převod nedeterministického automatu na deterministický =====

<box 90% round green| Věta>Pro každý NFA //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) existuje ekvivalentní DFA.
</box>

Nedeterministický konečný automat je definován stejne jako deterministický automat s tím rozdílem, že přechodová funkce se definuje jako totální zobrazení do množiny všech podmnožin stavů. 

Jinými slovy z každého stavu může nedeterministický automat pod stejným vstupním symbolem přejít do různých stavů. 

Obecně algortimus převodu vypadá tak, že:

1.	Stavy nového automaty jsou z množiny všech podmnožin stavů Q.
2.	Přechodová funkce je z množiny podmnožin do množiny podmnožin Q a na pravé straně přechodové funkce je množina všech stavů Q, kam by se NFA mohl dostat. V další iteraci je pak na pravé straně množina všech stavů, kam by se NFA mohl dostat ze všech stavů z podmnožiny z předchozí iterace.
3.	Konečné stavy jsou pak ty, kde se v podmnožině vyskytuje alespoň jeden z koncových stavů z předchozího NFA.

==== Algoritmus transformace NFA na DFA ====
**Vstup**: NFA //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//).
**Výstup**: Ekvivalentní DFA //M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>', {//q<sub>0</sub>//}, //F//') bez nedosažitelných stavů a s totální přechodovou funkcí.

<box 90% | Algoritmus>//Q'// := { {//q<sub>0</sub>//} }; <m>delta</m>' := <m>varnothing</m>; //F'// := <m>varnothing</m>; //Done// := <m>varnothing</m>;
**while** (//Q'// -- //Done//) <m><>varnothing</m> **do**
//M// := libovolný prvek množiny //Q'// -- //Done//
**if** //M// <m>inter</m> //F// <m><>varnothing</m> **then** //F'// := //F'// <m>union</m> {//M//} **fi**
**foreach** //a// <m>in Sigma</m> **do**
//N// := <m>bigcup{p in M}{}{delta(p,a)}</m>
//Q'// := //Q'// <m>union</m> {//N//}
<m>delta</m>' := <m>delta</m>' <m>union</m> {( (//M//, //a//),//N//)} **od**
//Done// := //Done// <m>union</m> {//M//}
**od**
//M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>', {//q<sub>0</sub>//}, //F'//)
</box>

=== Příklad ===
Mějme nedeterministický konečný automat :

<box 500px left>{{:home:inf:automat_1.jpg|}}</box>

|     ^   a   ^   b   ^
^ -> 1|  1,2  |  1,7  |
^    2|   -   |   3   |
^    3|   -   |   4   |        
^    4|   5   |   -   |
^ <- 5|   5   |   5   |
^    6|   -   |   5   |
^    7|   6   |   -   | 

\\

Převod nedeterministického automatu na deterministický provedeme pomocí algoritmu následovně:
<box left 100% round orange|Praktické vysvětlení algoritmu>Začínáme vstupním stavem, který napíšeme do tabulky (**1**). Zjistíme množinu stavů, do kterých se dostaneme pomocí prvků abecedy. (**pro //a// 1,2**, **pro //b// 1,7**). Poté vždy vytvoříme (pokud ještě neexistuje) nový stav pojmenovaný jako sjednocení stavů (**pro //a// 12**, **pro //b// 17**) a zaznamenáme do tabulky. Vezmeme poté následující nezpracovaný stav v nově tvořené tabulce (**12**) a zjistíme do jaké množiny stavů se lze dostat ze stavů **1** a **2** a provedeme jejich sjednocení (**pro //a// 1,2** , **pro //b// 1,3,7**) poté opět zaznamenáme případný nový stav. Od této chvíle pokračujeme obdobně.
\\

Algoritmus končí, ve chvíli kdy není možné nalézt žádný nový stav. Vstupní stavy zůstávají stejné, koncové stavy jsou ty, které obsahují některý z původních koncových stavů.
</box>

Takto vytvořený automat nemusí být minimální, ale je bez nedosažitelných stavů, s totální přechodovou funkcí.
<box 560px left>{{:home:inf:automat_2.jpg|}}</box>

|       ^ a    ^  b   ^
^    -> 1| 12   | 17   | 
^      12| 12   | 137  |
^      17| 126  | 17   |
^     137| 126  | 147  |
^     126| 12   | 1357 |
^     147| 1256 | 17   |
^ <- 1357| 1256 | 1457 |
^ <- 1256| 125  | 1357 |
^ <- 1457| 1256 | 157  |  
^ <-  125| 125  | 1357 | 
^ <-  157| 1256 | 157  |

===== Vztah mezi konečnými automaty a regulárními jazyky =====


Platí věta, že pro každý jazyk popsatelný nějakým regulárním výrazem existuje automat, který jej rozpoznává.

Dále platí věta, že pokud je jazyk rozponávaný nějakým DFA, pak je popsatelný regulráním výrazem.

Tj. obě třídy jazyku jsou ekvivalentní (Kleeneho věta).



===== Pumping Lemma pro regulární jazyky =====
<box 90% round green|Lemma 2.13. (o vkládání)((viz skripta Automaty a formální jazyky I, str. 18))>Nechť //L// je regulární jazyk. Pak existuje číslo //n// <m>in</m> <m>bbN</m> takové, že všechna slova //w// <m>in</m> //L//, jejichž délka je alespoň //n//, lze psát ve tvaru //w// = //xyz//, kde |//xy//| ≤ //n//, //y// ≠ <m>epsilon</m> a //xy<sup>i</sup>z// <m>in</m> //L// pro každé //i// <m>in</m> <m>bbN</m><sub>0</sub>.
</box>

Je to prostředek jak dokázat, že nějaký daný jazyk **není regulární**. Představuje **nutnou** (nikoliv postačující) podmínku, kterou musí každý regulární jazyk splňovat. 
Pumping lemma prakticky říká, že v dostatečně dlouhém slově w, které patří do jistého jazyka, lze nalézt tři části x, y a z, přičemž y může být i celé slovo. y lze pak libovolně opakovat (napumpovat), či zcela vyloučit a výsledné slovo bude patřit do jazyka. Délka slova musí být větší nebo rovna pumpovací konstantě n a délka části xy musí být menší nebo rovna n.

Postupujeme tak, že ukážeme, že pokud platí obměna lemmatu o vkládání (jde o implikaci), potom jazyk L není regulární:

  * pro libovolné (všechna) //n// <m>in</m> <m>bbN</m> (pumpovací konstanta)
  * existuje takové //w// <m>in</m> //L// délky alespoň n, pro které platí, že
  * při libovolném (všech) rozdělení slova w na tři části x, y, z, že |xy| ≤ //n//, //y// ≠ <m>epsilon</m>
  * existuje alespoň jedno //i// <m>in</m> <m>bbN</m><sub>0</sub> takové, že //xy<sup>i</sup>z// <m>notin</m> //L//

Potom z lemmatu o vkládání plyne, že L není regulární.


Intuitivní důkaz tvrzení říká:

•	Pro konečné jazyky se jako pumpovací konstanta vezme délka nejdelšího slova.
•	Pro nekonečné jazyky musí existovat nějaký minimální konečný automat, který je akceptuje. Spočítá se počet jeho stavů a vezme se jako pumpovací konstanta p. Pokud automat akceptuje i slova delší než p, pak musí některými stavy procházet vicekrát. Jeden tento stav označíme S. Transakce, které automat posunou ze stavu S, a zpět do stavu S, akceptují nějaký řetězec. Tento řetězec je y v pumping lemmatu, tj. platí tvrzení lemma, že lze slovo nafukovat i že lze nafukování přeskočit rovnou dál.

====== Předměty ======
IB102 Automaty a gramatiky
IB005 Formální jazyky a automaty

====== 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ů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.

~~DISCUSSION~~