====== Úkol 1 ====== Bc. Jan Kaláb %%%% ===== Příklad 1 ===== **Uvažte jazyk //L₁// = {//aⁱb^j// | 0 < //i// ≤ //j// ∧ //i// + //j// = 2//k//, //k// ∈ ℕ}.** **Sestavte gramatiku //G₁// takovou, že //L//(//G₁//) = //L₁//.** //G₁// = ({//a//, //b//}, {//S//, //X//, //Y//}, //S//, //P//) //P// = { * //S// → //aXbY// * //X// → //aXb// | //ε// * //Y// → //bbY// | //ε// } **Jakého typu (dle Chomského hierarchie jazyků) je //G₁// a jakého typu je //L₁//? Mohou se tyto typy obecně lišit? Svoje tvrzení zdůvodněte.** //G₁// je typu 2, tedy //bezkontextová//, protože obsahuje pravidla ve tvaru //A// → //γ//, //A// ∈ //N//, //γ// ∈ (//N// ∪ //Σ//). Jazyk //L₁// navíc potřebuje "počítat", takže jistě nepůjde popsat omezenějším typem, než 2, protože ono "počítání" potřebuje zásobník. //L₁// je tedy podle definice 2.16 z opory (nebo 1.10 ze slajdů) také typu 2, tedy //bezkontextový//. __Obecně mohou.__ Tento jazyk by jistě bylo možno popsat i gramatikou typu 0, ale stále by to byl stejný (typu 2) jazyk. Je ale zvykem, že se typ jazyka i gramatiky shoduje. ===== Příklad 2 ===== **Uvažte regulární výraz //r₂// = (//ab// + //ε//)* //a//* //c//.** **Převeďte //r₂// algoritmicky na redukovaný deterministický konečný automat //M₂// (tj. RV → RKA → DKA → redukovaný DKA), přijímající jazyk popsaný výrazem //r₂//.** Podle algoritmů 3.4, 3.5 a 3.7 z opory. Strom RV:\\ {{regexptree.png?300|Strom RV}} RKA:\\ {{rka.png?600|RKA}} Nejsou zde žádné nedosažitelné stavy. Úplně definovaný DKA: ^ ^ ^ ε-uz ^ //a// ^^ //b// ^^ //c// ^^ | →I | {1} | {1, 2, 3, 6, 7, 8, 9, 10, 12} | {4, 11} | II | ∅ | T | {13} | III | | II | {4, 11} | {4, 10, 11, 12} | {11} | IV | {5} | V | {13} | III | | III→ | {13} | {13} | ∅ | T | ∅ | T | ∅ | T | | IV | {11} | {10, 11, 12} | {11} | IV | ∅ | T | {13} | III | | V | {5} | {2, 3, 5, 6, 7, 8, 9, 10, 12} | {4, 11} | II | ∅ | T | {13} | III | | T | | {T} | T |||||| {{udka.png?300|Úplně definovaný DKA}} Minimalizace: ^ ≡⁰ ^^ //a// ^^ //b// ^^ //c// ^^ | A→ | III→ | T | B | T | B | T | B | | →B | →I | II | B | T | B | III | A | |:::| V | II |:::| T |:::| III |:::| |:::| II | IV |:::| V |:::| III |:::| |:::| IV | IV |:::| T |:::| III |:::| |:::| T | T | B | T | B | T | B | ^ ≡¹ ^^ //a// ^^ //b// ^^ //c// ^^ | A→ | III→ | T | T | T | T | T | T | | →B | →I | II | B | T | C | III | A | |:::| V | II |:::| T |:::| III |:::| |:::| IV | IV |:::| T |:::| III |:::| |:::| II | IV | B | V | B | III | A | | T | T | T | T | T | T | T | T | ^ ≡² ^^ //a// ^^ //b// ^^ //c// ^^ | A→ | III→ | T | T | T | T | T | T | | →B | →I | II | C | T | T | III | A | |:::| V | II |:::| T |:::| III |:::| |:::| IV | IV | B | T | T | III | A | | C | II | IV | B | V | B | III | A | | T | T | T | T | T | T | T | T | ^ ≡³ ^^ //a// ^^ //b// ^^ //c// ^^ | A→ | III→ | T | T | T | T | T | T | | →B | →I | II | C | T | T | III | A | |:::| V | II |:::| T |:::| III |:::| | C | II | IV | D | V | B | III | A | | D | IV | IV | D | T | T | III | A | | T | T | T | T | T | T | T | T | ≡³ = ≡⁴ = ≡ {{rdka.png?300|Redukovaný DKA}}((//Sink// stav je pro přehlednost vynechán)) **Převeďte automat //M₂// na redukovaný deterministický konečný automat //M₂′// přijímající komplement jazyka (nad abecedou {//a//, //b//, //c//}) popsaného výrazem //r₂//.** {{complement.png?300|Redukovaný DKA přijímající komplement jazyka}} ===== Příklad 3 ===== **Uvažte NKA //M₃// 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.** //Stavy jsem si označil X, Y, Z ve směru z leva.// * //X// = //aY// + //aZ// * //Y// = //aY// + //bZ// + //ε// * //Z// = //bX// * //X// = //aY// + //abX// = //abX// + //aY// * //Y// = //aY// + //bbX// + //ε// * //X// = (//ab//)*//aY// * //Y// = //a//*(//bbX// + //ε//) * //X// = (//ab//)*//a//(//a//*(//bbX// + //ε//)) * //X// = (//ab//)*//aa//*(//bbX// + //ε//) * //X// = (//ab//)*//a//⁺(//bbX// + //ε//) * //X// = (//ab//)*//a//⁺//bbX// + (//ab//)*//a//⁺ * //X// = ((//ab//)*//a//⁺//bb//)*(//ab//)*//a//⁺ * //X// = (//ab// + //a//⁺//bb//)*//a//⁺ ===== Příklad 4 ===== **Nechť //M₁// = {//Q//, Σ, //δ//, //q₀//, //F//} je nedeterministický konečný automat. Mějme funkci Φ: Σ* → (Σ ∪ {•})*, kde • ∉ Σ, definovanou následujícím předpisem** * **Φ(//ε//) = //ε//** * **Φ(//a₁//) = //a₁//, kde //a₁// ∈ Σ** * **Φ(//a₁a₂u//) = //a₁a₂// • Φ(//u//), kde //a₁//, //a₂// ∈ Σ, //u// ∈ Σ*** **Například: Φ(//aa//) = //aa//•, Φ(//abcde//) = //ab//•//cd//•//e//** **Navrhněte a //formálně popište// algoritmus, který má na vstupu automat //M₁//, a jehož výstupem bude (nedet.) konečný automat //M₂// takový, že //L//(//M₂//) = {Φ(//w//) | //w// ∈ //L//(//M₁//)}.** Vstup: NKA //M₁// = (//Q//, //Σ//, //δ//, //q//₀, //F//)\\ Výstup: NKA //M₂// = (//Q//′, //Σ//′, //δ//′, //q//₀′, //F//′) * //Q//′ = {(//q//₀, //n//) | //q//₀ ∈ //Q//; //n// ∈ {0, 1, 2}} * //Σ//′ = //Σ// ∪ {•} * //q//₀′ = (//q//₀, 0) * //F//′ = {(//q//, //n//) | //q// ∈ //F//; //n// ∈ {0, 1}} * //δ//′ = ∀//a// ∈ //Σ//; ∀//q//₁, //q//₂ ∈ //Q//: * //δ//(//q//₁, //a//) = //q//₂ → * //δ//′((//q//₁, 0), //a//) = {(//q//₂, 1)} ∪ //δ//′((//q//₁, 0) * //δ//′((//q//₁, 1), //a//) = {(//q//₂, 2)} ∪ //δ//′((//q//₁, 1) * //δ//′((//q//₁, 2), •) = {(//q//₁, 0)} ∪ //δ//′((//q//₁, 2), •) ===== Příklad 5 ===== **Mějme jazyk //L// = {//w// | //w// ∈ {//a//, //b//, //c//}* ∧ #_//a//(//w//) = #_//b//(//w//) ∧ #_//c//(//w//) = 1}, kde #_//x//(//w//) je počet symbolů //x// ve slově //w//. Je jazyk //L// regulární? Dokažte nebo vyvraťte.** Předpokládejme, že //L// je regulární. Pak musí platit: ∃//p// > 0: ∀//w// ∈ //L//: |//w//| ≥ //p// ⇒ ∃//x//, //y//, //z// ∈ Σ*: //w// = //xyz// ∧ 0 < |//y//| ≤ //p// ∧ ∀//i// ≥ 0: //xyⁱz// ∈ //L//. Uvažujme slova //w// ve tvaru //a^pcb^p//. |//w//| ≥ //p//. Pak lze při //i// ≠ 1 zvolit //y// následujícími způsoby: * //a**a…a**acbb…bb//: #_//a//(//w//) ≠ #_//b//(//w//) * //aa…aacb**b…b**b//: #_//a//(//w//) ≠ #_//b//(//w//) * //c// ∈ //y//: #_//c//(//w//) ≠ 1 Nelze tedy najít takové rozdělení //xyz//, které by uspokojilo podmínky pumping lemmatu, jazyk tedy není regulární. ===== Příklad 6 ===== **Uvažujme algebru regulárních množin (//A_RM//) nad abecedou Σ.** **Ukažte, že pro //A_RM// platí následující vztah: //A//*//A//* = //A//*, kde //A// je libovolná regulární množina. Nepoužívejte fakt, že //A_RM// je Kleeneho algebrou.** - Ukážeme, že //A//*//A//* ⊆ //A//* * Ukážeme, že ∀//w// ∈ //A//*//A//*: //w// ∈ //A//* * Uvažme livobolné //w// ∈ //A//*//A//* * Dle definice ., //w// = //w//₁ . //w//₂ pro //w//₁ ∈ //A//* a //w//₂ ∈ //A//* * Dle definice *, //w//₁ = //w//₁¹ . //w//₂¹ . … . //w_n//¹ pro //n// ≥ 0, //w_i//¹ ∈ //A// pro 1 ≤ //i// ≤ //n// a podobně //w//₂ = //w//₁² . //w//₂² . … . //w_m//² pro //m// ≥ 0, //w_i//² ∈ //A// pro 1 ≤ //i// ≤ //m// * Z definic . a *, //w//₁¹ . … . //w_n//¹ . //w//₁² . … . //w_m//² ∈ //A//* - Ukážeme, že //A//* ⊆ //A//*//A//* * Ukážeme, že ∀//w// ∈ //A//*: //w// ∈ //A//*//A//* * Uvažme livobolné //w// ∈ //A//* * Víme, že //ε// ∈ //A//* * //w// . //ε// ∈ //A//*//A//* dle definice . jazyků ∧ //w// . //ε// = //w// z definice . řetězců a tedy //w// ∈ //A//*//A//* **Určete, zdali je ⊆ //totální uspořádání// v //A_RM//. Tedy že pro libovolné dvě regulární množiny //A// a //B// platí vždy alespoň jedna z nerovností //A// ⊆ //B// nebo //B// ⊆ //A//. Své tvrzení dokažte.** Uvažme regulární množiny //A// = {//a//} a //B// = {//b//}. Neplatí pro ně ani jedna z nerovností //A// ⊆ //B// nebo //B// ⊆ //A//, ⊆ tedy **není** //totální uspořádání// v //A_RM//.