Regular language

Jazyk je regulární tehdy, pokud existuje konečný automat, který akceptuje právě všechna slova z jazyka L.

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é.

• Pumping lemma – používá se k dokazování, že daný jazyk NENÍ regulární.

• 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í jazyk je definován regulární gramatikou.

Je to čtveřice:¹⁾

• 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)

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₀, q₁, q₂}, {a, b}, δ, q₀, {q₀, q₂})

• δ(q₀, a) = q₂
• δ(q₁, b) = q₁
• δ(q₂, a) = q₀

• 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.

• Pokud má nedeterministický konečný automat n stavů, bude jeho deterministická varianta mít nejvíce 2ⁿ 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í).

1. Dostaneme zadaný graf, nebo rovnou tabulku.
   • Graf přepíšeme do tabulky.

Teď opíšeme první řadek.

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.

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.

Regular expression

• L²⁾(ε) = {ε}
• L(∅) = ∅
• L(a) = {a}
• L(E . F) = L(E) . L(F)
• L(E + F) = L(E) ∪ L(F)
• L(E*) = L(E)*

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

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

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řevedeme minule vytvořený konečný automat zpět na regulární výraz.

Ještě bysme mohli odstranit ε přechody

• 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í