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

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:

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

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

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.

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

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í