====== Úkol 1 ======
Bc. Jan Kaláb %%<xkalab00@stud.fit.vutbr.cz>%%
===== Příklad 1 =====
**Uvažte jazyk //L<sub>1</sub>// = {//a<sup>i</sup>b<sup>j</sup>c<sup>i+j</sup>// | //i// ≥ 0, //j// ≥ 0}.**

**Sestavte gramatiku //G<sub>1</sub>// takovou, že //L//(//G<sub>1</sub>//) = //L<sub>1</sub>//.**

//G<sub>1</sub>// = ({//a//, //b//, //c//}, {//S//, //A//, //B//}, //S//, //P//)\\
//P// = {
  * //S// → //A//
  * //A// → //aAc// | //B//
  * //B// → //bBc// | //ε//
}

**Jakého typu (dle Chomského hierarchie jazyků) je //G<sub>1</sub>// a jakého typu je //L<sub>1</sub>//? Mohou se tyto typy obecně lišit? Svoje tvrzení zdůvodněte.**

__//G<sub>1</sub>// i //L<sub>1</sub>// jsou bezkontextové.__ //G<sub>1</sub>// má pravidla ve tvaru "neterminál → posloupnost terminálů a neterminálů". //L<sub>1</sub>// lze reprezentovat zásobníkovým automatem (ale ne konečným automatem).

Obecně se lišit mohou. Chomského hierarchie jazyků a gramatik má strukturu "vrstev" -- bezkontextové gramatiky lze popsat i jako kontextové či obecné, ale ne jako regulární. To samé platí i pro jazyky. Důsledkem je, že bezkontextový jazyk jistě půjde popsat kontextovou gramatikou.
===== Příklad 2 =====
**Uvažte regulární výraz //r<sub>2</sub>// = (//ab// + //abc//)* //ab//*.**

**Převeďte //r<sub>2</sub>// algoritmicky na minimální deterministický konečný automat //M<sub>2</sub>// (tj. RV → RKA → DKA → minimální DKA), přijímající jazyk popsaný výrazem //r<sub>2</sub>//.**

Strom pro RV:\\
{{regexptree.png?300}}

RKA ze stromu RV:\\
{{rka.png?600|RKA}}

Úplně definovaný DKA:
^ ^  //a//  ^  //b//  ^  //c//  ^
|→ε-uz({1}) = {1, 2, 3, 6, 11} = A|ε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = B|ε-uz({}) = ∅ = T|ε-uz({}) = ∅ = T|
|←B|ε-uz({}) = ∅ = T|ε-uz({5, 8, 14}) = {2, 3, 5, 6, 8, 10, 11, 13, 14, 15} = C|ε-uz({}) = ∅ = T|
|←C|ε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = B|ε-uz({14}) = {13, 14, 15} = D|ε-uz({9}) = {2, 3, 6, 9, 10, 11} = E|
|←D|ε-uz({}) = ∅ = T|ε-uz({14}) = {13, 14, 15} = D|ε-uz({}) = ∅ = T|
|E|ε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = B|ε-uz({}) = ∅ = T|ε-uz({}) = ∅ = T|
|T|T|T|T|

{{dka.png?300|DKA}}

Minimalizace:
^  ≡<sup>0</sup>  ^^  //a//  ^^  //b//  ^^  //c//  ^^
|  ←I  |  ←B  |  T  |  II  |  C  |  I  |  T  |  II  |
|:::|  ←D  |:::|:::|:::|:::|:::|:::|
|:::|  ←C  |  B  |  I  |  D  |  I  |  E  |  II  |
|  →II  |  →A  |  B  |  I  |  T  |  II  |  T  |  II  |
|:::|  E  |:::|:::|:::|:::|:::|:::|
|:::|  T  |  T  |  II  |  T  |  II  |  T  |  II  |

^  ≡<sup>1</sup>  ^^  //a//  ^^  //b//  ^^  //c//  ^^
|  ←I  |  ←B  |  T  |  IV  |  C  |  II  |  T  |  IV  |
|:::|  ←D  |  T  |  IV  |  D  |  I  |  T  |  IV  |
|  ←II  |  ←C  |  B  |  I  |  D  |  I  |  E  |  III  |
|  →III  |  →A  |  B  |  I  |  T  |  IV  |  T  |  IV  |
|:::|  E  |:::|:::|:::|:::|:::|:::|
|  IV  |  T  |  T  |  IV  |  T  |  IV  |  T  |  IV  |

^  ≡<sup>2</sup>  ^^  //a//  ^^  //b//  ^^  //c//  ^^
|  ←I  |  ←B  |  T  |  V  |  C  |  III  |  T  |  V  |
|  ←II  |  ←D  |  T  |  V  |  D  |  II  |  T  |  V  |
|  ←III  |  ←C  |  B  |  I  |  D  |  II  |  E  |  IV  |
|  →IV  |  →A  |  B  |  I  |  T  |  V  |  T  |  V  |
|:::|  E  |:::|:::|:::|:::|:::|:::|
|  V  |  T  |  T  |  V  |  T  |  IV  |  T  |  IV  |

≡<sup>2</sup> = ≡<sup>3</sup> = ≡

{{mka.png?300|Minimální DKA}}

**Převeďte automat //M<sub>2</sub>// na minimální deterministický konečný automat //M<sub>2</sub>′// přijímající komplement jazyka (nad abecedou {//a//, //b//, //c//}) popsaného výrazem //r<sub>2</sub>//.**

{{comp.png?300|M2′}}
===== Příklad 3 =====
**Uvažte NKA //M<sub>3</sub>// nad abecedou Σ = {//a//, //b//} z obrázku 1:\\ {{ 1.png?300 |Obrázek 1: NKA M3}}\\ Řešením rovnic nad regulárními výrazy sestavte k tomuto automatu ekvivalentní regulární výraz.**

//Pozn.: Stavy jsem si označil X, Y, Z ve směru z leva.//

  * //X = aY + aZ + ε//
  * //Y = aY + bZ//
  * //Z = aZ + bX//

  * //X = aY + aZ + ε//
  * //Y = a*bZ//
  * //Z = a*bX//

  * //X = aa*bZ + aa*bX + ε//
  * //X = aa*ba*bX + aa*bX + ε//
  * //X = //(//aa*ba*b + aa*b//)//X + ε//
  * //X = //(//aa*ba*b + aa*b//)//*ε//

__(//a<sup>+</sup>ba*b + a<sup>+</sup>b//)*__
===== Příklad 4 =====
**Mějme operaci //even// : Σ* → Σ*, která z daného slova //w// ∈ Σ* vybere pouze znaky na sudých pozicích. Například: //even//(//abcda//) = //bd//, //even//(//aabbcc//) = //abc//.**

**Navrhněte a //formálně popište// algoritmus, který má na vstupu nedeterministický konečný automat //M<sub>1</sub>//, a jehož výstupem bude automat //M<sub>2</sub>// takový, že //L//(//M<sub>2</sub>//) = {//even//(//w//) | //w// ∈ //L//(//M<sub>1</sub>//)}.**

Vstup: NKA //M<sub>1</sub>// = (//Q<sub>1</sub>//, //Σ<sub>1</sub>//, //δ<sub>1</sub>//, //q<sub>0</sub><sup>1</sup>//,  //F<sub>1</sub>//)\\
Výstup: //M<sub>2</sub>// = (//Q<sub>2</sub>//, //Σ<sub>2</sub>//, //δ<sub>2</sub>//, //q<sub>0</sub><sup>2</sup>//,  //F<sub>2</sub>//)

  - //Q<sub>2</sub> ⊆ Q<sub>1</sub>//
  - //Σ<sub>2</sub> ⊆ Σ<sub>1</sub>//
  -
    - //∀q<sub>1</sub><sup>1</sup>//, //q<sub>2</sub><sup>1</sup>//, //q<sub>3</sub><sup>1</sup> ∈ Q<sub>1</sub>//\\ //∀q<sub>1</sub><sup>2</sup>//, //q<sub>2</sub><sup>2</sup> ∈ Q<sub>2</sub>//\\ //∀a//, //b ∈ Σ<sub>1</sub> ∧ ∀b ∈ Σ<sub>2</sub>//:\\ //q<sub>2</sub><sup>2</sup> ∈ δ<sub>2</sub>//(//q<sub>1</sub><sup>2</sup>//, //b//) ⇔ (//δ<sub>1</sub>(q<sub>1</sub><sup>1</sup>//, //a//) = //q<sub>2</sub><sup>1</sup> ∧ δ<sub>1</sub>//(//q<sub>2</sub><sup>1</sup>//, //b//) = //q<sub>3</sub><sup>1</sup>//)
    - //∀q<sub>1</sub><sup>1</sup>//, //q<sub>2</sub><sup>1</sup> ∈ Q<sub>1</sub> ∧ q<sub>2</sub><sup>1</sup> ∈ F<sub>1</sub>//\\ //∀q<sub>1</sub><sup>2</sup>//, //q<sub>2</sub><sup>2</sup> ∈ Q<sub>2</sub>//\\ //∀a ∈ Σ<sub>1</sub>//:\\ //q<sub>2</sub><sup>2</sup> ∈ δ<sub>2</sub>//(//q<sub>1</sub><sup>2</sup>//, //ε//) ⇔ (//δ<sub>1</sub>(q<sub>1</sub><sup>1</sup>//, //a//) = //q<sub>2</sub><sup>1</sup> ∧ δ<sub>1</sub>//(//q<sub>2</sub><sup>1</sup>//, //ε//) = //q<sub>2</sub><sup>1</sup>//)
  - //q<sub>0</sub><sup>1</sup> = q<sub>0</sub><sup>2</sup>//
  - //F<sub>2</sub> = F<sub>1</sub>//
===== Příklad 5 =====
**Mějme jazyk //L// = {//a<sup>i</sup>b<sup>j</sup>a<sup>2i</sup>// | 0 ≤ //i//, 0 ≤ //j// ≤ 5}. Je jazyk //L// regulární? Dokažte nebo vyvraťte.**

==== Lemma ====
Nechť //L// je regulární jazyk. Pak existuje //n// ∈ **N** takové, že libovolné slovo //w ∈ L// délky alespoň //n// lze psát ve tvaru //w = xyz//, kde |//xy//| ≤ //n//, //y// ≠ //ε// a //xy<sup>i</sup>z ∈ L// pro každé //i// ∈ **N**<sub>0</sub>.

==== Řešení ====
Budeme provádět důkaz sporem. Předpokládejme, že //L// je regulární.

Z uvedené pumping lemmy a z předpokladu plyne, že musí existovat konstanta //n//.

Uvažujme libovolnou hodnotu //n//.

Pro //w// = //a<sup>n</sup>b<sup>4</sup>a<sup>2n</sup>// náležící //L//, platí |//w//| ≥ //n//.

Uvažujme libovolný výběr //x//, //y//, //z// takový, že //w = xyz// ∧ |//xy//| ≤ //n// ∧ //y// ≠ //ε//.

Uvažujme například rozdělení:
  * //x// = //a<sup>m</sup>//
  * //y// = //a<sup>n−m</sup>//
  * //z// = //b<sup>4</sup>a<sup>2n</sup>//
Pro //i// = 2 platí: //xy<sup>i</sup>z// = //a<sup>2n−m</sup>b<sup>4</sup>a<sup>2n</sup>// ∉ //L// protože, //2n − m ≠ 2n//.

Obdobně lze dokázat pro libovolná jiná rozdělení //w = xyz// se stejnou pumpovací konstantou //i// = 2.

Dochází ke sporu, protože //w// po pumpování nenáleží do jazyka //L// a tedy //L// __není regulární__.

===== Příklad 6 =====
**Uvažujme algebru regulárních množin (//A<sub>RM</sub>//) nad abecedou Σ.**

**Ukažte, že pro //A<sub>RM</sub>// platí následující teorém Kleeneho algebry: //a//(//ba//)* = (//ab//)*//a//.**

{{kleene.png}}

Výše uvedený konečný automat je minimální konečný automat který přijímá i zamítá stejné řetězce jako regulární výraz na levé i pravé straně teorému. Proto je teorém platný.

**Vzhledem k uspořádání definovaném v Kleeneho algebře určete, zdali je {//ε//} minimálním prvkem //A<sub>RM</sub>//. Své tvrzení dokažte.**

Předpokládejme, že {//ε//} je minimálním prvkem //A<sub>RM</sub>//. Pak by vzhledem k uspořádání definovaném v Kleeneho algebře muselo platit: {//ε//} ∪ {//a//} = {//a//}. Ovšem {//ε//} ∪ {//a//} = {//ε//, //a//}. Dochází tedy ke sporu, tedy __{//ε//} není minimálním prvkem //A<sub>RM</sub>//__.