no way to compare when less than two revisions

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

@@ Řádek 1: / Řádek 1: @@
+====== Regulární jazyky a jejich modely ======
+[[wp>Regular language]]
+Jazyk je regulární tehdy, pokud existuje konečný automat, který akceptuje **právě** všechna slova z jazyka L.
+===== Uzávěrové vlastnosti =====
+**Množina uzavřená na operaci** -- Vezmu dva prvky z množiny (přirozená čísla), provedu s nimi operaci (sečtu je) a výsledek bude zase prvek z té samé množiny (zase přirozené číslo)
+Regulární jazyk je uzavřen na skoro všechny operace, ale musí být konečné.
+===== Důkaz, že jazyk je regulární =====
+  * Pumping lemma -- používá se k dokazování, že daný jazyk NENÍ regulární.
+===== Pojmy =====
+  * **Prázdné slovo** (ε) -- Prázdný řetězec, který ale vyhovuje jazyku (je možné jej vygenerovat/přijmout)!
+  * **Řetězec** -- jakákoli posloupnost terminálních i netereminálních symbolů (znaků)
+  * **Větná forma** -- řetězec, který lze odvodit z počátečního symbolu gramatiky
+  * **Věta** -- větná forma pouze z terminálních symbolů
+  * **Jazyk** -- podmnožina všech řetězců nad abecedou (L ⊆ Σ)
+===== Regulární gramatika =====
+Regulární jazyk je definován regulární gramatikou.
+Je to čtveřice:((Jako u každé gramatiky))
+  * Konečná množina terminálních symbolů (T, abeceda)
+  * Konečná množina neterminálních symbolů (N)
+  * Konečná množina pravidel (P)
+  * Počáteční symbol (S)
+Příklad: G = ({a, b}, {A, B, C}, P, A)\\
+P = {
+  * A -> ε | aB
+  * B -> bC
+  * C -> a
+}
+Pravidla musí být ve tvaru "neterminál -> terminál a neterminál" nebo "neterminál -> terminál"! Vyjímkou je počáteční symbol gramatiky, který může být přepsán na prázdné slovo, ale pak se počáteční symbol nesmí vyskytovat na pravé straně pravidla.
+"Odvození" = použití pravidla (přímé -- jedno pravidlo, v //k// krocích -- //k// pravidel)
+===== Konečné automaty =====
+[[wp>Finite-state machine]]
+Je to pětice:
+  * Neprázdná konečná množina stavů (Q)
+  * Konečná vstupní abeceda (T)
+  * Parciální přechodová funkce (δ: Q × T -> Q, je možné ji zadat grafem, tabulkou nebo výčtem)
+  * Počáteční stav (s ∈ Q)
+  * Množina akceptujících stavů (F ⊆ Q)
+Příklad: A = ({q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>}, {a, b}, δ, q<sub>0</sub>, {q<sub>0</sub>, q<sub>2</sub>})
+  * δ(q<sub>0</sub>, a) = q<sub>2</sub>
+  * δ(q<sub>1</sub>, b) = q<sub>1</sub>
+  * δ(q<sub>2</sub>, a) = q<sub>0</sub>
+  * Deterministický -- nejvíce jeden přechod pod jedním znakem (u každého stavu)
+  * Nedetrministický -- více přechodů pod jedním znakem
+  * S ε-kroky -- je možné nenačítat další symbol, a přejít ze stavu do stavu pod znakem ε
+Automaty jsou **ekvivalentní** pokud přijímají i zamítají stejná slova.
+Může skončit třemi stavy:
+  - Po přečtení slova skončíme v některém z koncových (akceptujících) stavů -- v takovém případě je slovo přijato.
+  - Po přečtení slova skončíme v jiném než koncovém stavu -- slovo je zamítnuto.
+  - Nedočteme slovo (někde uprostřed slova se dostaneme do stavu, kdy nejsme schopni zpracovat další znak protože neexistuje pro ten znak přechod) -- slovo je zamítnuto.
+==== Determinizace ====
+  * Pokud má nedeterministický konečný automat //n// stavů, bude jeho deterministická varianta mít nejvíce 2<sup>//n//</sup> stavů.
+  * Každý nedeterministický konečný automat má svoji deterministickou variantu.
+  * Deterministický konečný automat nemusí být minimální (a většinou ani není).
+=== Příklad ===
+{{determinizace_in.png}}
+  - Dostaneme zadaný graf, nebo rovnou tabulku.
+    * Graf přepíšeme do tabulky.
+^     ^  //a//   ^    //b//    ^
+|  →1 |    ∅     |   {2, 3}    |
+|   2 |  {1, 6}  |     {7}     |
+|   3 |    ∅     |  {4, 5, 7}  |
+|  ←4 |   {6}    |    {2, 8}   |
+|   5 |   {1}    |      ∅      |
+|   6 |   {6}    |      ∅      |
+|   7 |    ∅     |     {8}     |
+|  ←8 |   {1}    |    {4, 5}   |
+Teď opíšeme první řadek.
+^     ^  //a//   ^    //b//    ^
+|  →1 |    ∅     |   {2, 3}    |
+V něm je stav {2, 3}, připíšeme ho tedy do tabulky. Pak se podíváme do první tabulky, do jakých stavů se můžeme ze stavů 2 a 3 dostat, pokud příjmeme //a// nebo //b//.
+^         ^  //a//   ^    //b//    ^
+|      →1 |    ∅     |   {2, 3}    |
+|  {2, 3} |  {1, 6}  |  {4, 5, 7}  |
+Teď nám tu přibyly 2 nové stavy ({1, 6} a {4, 5, 7}), uděláme tedy opět to samé co v minulém kroku. Tohle budeme opakovat neustále dokola, dokud nebudeme mít všechny stavy. Pokud je v tom novém stavu nějký stav který byl koncovým (např. 4  v {4, 5, 7}), bude i ten nový stav koncovým.
+^             ^  //a//   ^    //b//    ^
+|        →{1} |    ∅     |   {2, 3}    |
+|      {2, 3} |  {1, 6}  |  {4, 5, 7}  |
+|      {1, 6} |   {6}    |   {2, 3}    |
+|  ←{4, 5, 7} |  {1, 6}  |   {2, 8}    |
+|         {6} |   {6}    |     ∅       |
+|     ←{2, 8} |  {1, 6}  |  {4, 5, 7}  |
+{{determinizace_out.png}}
+===== Regulární výrazy =====
+[[wp>Regular expression]]
+<note important>
+Některé symboly tu fungují jinak než POSIX regexpy!
+  * **a . b** -- konkatenace / zřetězení (jako v PHP)
+  * **a + b** -- nebo, OR
+  * **a<sup>*</sup>**, **a<sup>+</sup>** -- iterace (zřetězení)
+</note>
+  * L((L je jazyk))(ε) = {ε}
+  * L(∅) = ∅
+  * L(a) = {a}
+  * L(E . F) = L(E) . L(F)
+  * L(E + F) = L(E) ∪ L(F)
+  * L(E*) = L(E)*
+==== Převod regulárního výrazu na konečný automat ====
+Nejdřív uděláme počáteční a koncový stav a mezi ně na přechod napíšeme regexp. Ten pak postupně (směrem zvenku dovnitř) rozgenerováváme podle následujících pravidel dokud není na každé hraně právě jeden symbol.
+^  Vstup  ^  Výstup  ^
+|  {{regexp_or_in.png|a + b}}  |  {{regexp_or_out.png|a + b}}  |
+|  {{regexp_cat_in.png|a . b}}  |  {{regexp_cat_out.png|a . b}}  |
+|  {{regexp_iter_in.png|a*}}  |  {{regexp_iter_out.png|a*}}  |
+=== Příklad ===
+**b ((aab<sup>*</sup> + aaaa) b)<sup>*</sup> a**
+{{re2ko_1.png|Rozgenerujeme okrajové konkatenace}}\\
+{{re2ko_2.png|Iterace závorky}}\\
+{{re2ko_3.png|Konkatenace (je v iteraci!)}}\\
+{{re2ko_4.png|OR}}\\
+{{re2ko_5.png|Konkatenace áček}}\\
+{{re2ko_6.png|Recyklujeme první dvě áčka a přidáme iteraci béčka}}
+==== Převod konečného automatu na regulární výraz ====
+  - Automat "obalíme" novým počátečním a koncovým stavem na které přes ε přechody navážeme ty staré.
+  - Pak postupně škrtáme uzly grafu a nahrazujeme je hranami, podle dříve uvedených pravidel, ale v opačném pořadí.
+  - Opakujeme krok 2 dokud nedostaneme jen počáteční a koncový stav s jednou hranou která představuje regulární výraz.
+=== Příklad ===
+Převedeme minule vytvořený konečný automat zpět na regulární výraz.
+{{ko2re_1.png|Obalíme do nových počátečních a koncových stavů}}\\
+{{ko2re_2.png|Sloučíme áčka a iteraci}}\\
+{{ko2re_3.png|Odtraníme uzel 6 (OR)}}\\
+{{ko2re_4.png|Odtraníme uzel 4 (zřetězení)}}\\
+{{ko2re_5.png|Odtraníme uzel 3 (iterace)}}\\
+{{ko2re_6.png|Odtraníme uzly 1 a 2 (zřetězení)}}
+Ještě bysme mohli odstranit ε přechody 8-)
+===== Shrnutí =====
+  * regulární jazyk: formální jazyk, generován regulární gramatikou, existuje konečný automat, který přijme právě všechna slova z jazyka
+  * dva modely: konečný automat, regulární výraz
+  * jeden lze převést na druhý
+  * regulární gramatika: čtveřice (viz výše), pravidla: neterminál -> terminál a neterminál, možno vypustit druhý neterminál, odvození
+  * konečný automat: pětice (viz výše), determinismus, ekvivalence, umět nakreslit a převést na reg. výraz
+  * regulární výraz: jiný model regulárního jazyka, lze převést na konečný automat, konkatenace ., zřetězení (+ vs *), "nebo" +, umět napsat a převést
+  * lze použít pumping lemmu na dokázání, že jazyk není regulární

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku