Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:regularni_jazyky

Regulární jazyky a jejich modely

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:1)

  • 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

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 = ({q0, q1, q2}, {a, b}, δ, q0, {q0, q2})

  • δ(q0, a) = q2
  • δ(q1, b) = q1
  • δ(q2, a) = q0
  • 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:

  1. 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.
  2. Po přečtení slova skončíme v jiném než koncovém stavu – slovo je zamítnuto.
  3. 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 2n 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

  1. 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}

Regulární výrazy

Regular expression

Některé symboly tu fungují jinak než POSIX regexpy!
  • a . b – konkatenace / zřetězení (jako v PHP)
  • a + b – nebo, OR
  • a*, a+ – iterace (zřetězení)
  • L2)(ε) = {ε}
  • 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
a + b a + b
a . b a . b
a* a*

Příklad

b ((aab* + aaaa) b)* a

Rozgenerujeme okrajové konkatenace
Iterace závorky
Konkatenace (je v iteraci!)
OR
Konkatenace áček
Recyklujeme první dvě áčka a přidáme iteraci béčka

Převod konečného automatu na regulární výraz

  1. Automat „obalíme“ novým počátečním a koncovým stavem na které přes ε přechody navážeme ty staré.
  2. Pak postupně škrtáme uzly grafu a nahrazujeme je hranami, podle dříve uvedených pravidel, ale v opačném pořadí.
  3. 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.

Obalíme do nových počátečních a koncových stavů
Sloučíme áčka a iteraci
Odtraníme uzel 6 (OR)
Odtraníme uzel 4 (zřetězení)
Odtraníme uzel 3 (iterace)
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í
1)
Jako u každé gramatiky
2)
L je jazyk
/var/www/wiki/data/pages/pitel/isz/regularni_jazyky.txt · Poslední úprava: 03. 07. 2012, 13.53:47 (upraveno mimo DokuWiki)