Formální jazyky I

Note	Chomského hierarchie formálních jazyků. Regulární jazyky, jejich reprezentace a převody mezi nimi. Varianty konečných automatů. Nedeterminismus a determinizace automatů. Uzávěrové vlastnosti regulárních jazyků. IB102/IB005

Formální jazyk $L$ je množina slov — posloupností znaků z konečné abecedy $Σ$ (taky množina), které vznikly aplikací daných pravidel.

Gramatika $G$

Čtveřice $(N, Σ, P, S)$ , kde

$N$ je neprázdná množina neterminálů,
$Σ$ je konečná množina terminálů (abeceda) taková, že $N \cap Σ = \emptyset$ ,
( $V = N \cup Σ$ ),
$P \subseteq V^{*} . N . V^{*} \times V^{*}$ je konečná množina pravidel,
$S \in N$ je počáteční neterminál.

Terminály značíme malými písmeny, neterminály velkými. Pravidla zapisujeme $α A β \to γ$ .

Chomského hierarchie jazyků

Definovaná požadavky na tvar pravidel gramatik.

Typ 0 (frázové jazyky): Žádná omezení na pravidla. Pro každý jazyk typu 0 lze sestrojit Turingův stroj, který jej rozhoduje.
Typ 1 (kontextové jazyky): Pravidla mohou levý i pravý kontext ( $α$ a $β$ ): $α A β \to α γ β$ , který zachovávají. $∣ γ ∣ \geq 1$ .
Typ 2 (bezkontexové jazyky): $A \to α, ∣ α ∣ \geq 1$ s výjimkou $S \to ε$ , pokud $S$ není na pravé straně žádného pravidla.
Typ 3 (regulární jazyky): $A \to a$ a $A \to a B$ nebo ekvivaletně $A \to a$ a $A \to B a$ . Výjimkou je $S \to ε$ , pokud $S$ není na pravé straně žádného pravidla.

Regulární jazyky

Lze je reprezentovat

regulární gramatikou,
deterministickým konečným automatem (DFA),
nedeterministickým konečným automatem (NFA),
nedeterministickým konečným automatem s $ε$ -kroky ( $ε$ NFA),
regulárním přechodovým grafem (RTG),
regulárním výrazem (RE).

Lze převádět

Deterministický konečný automat (DFA)

Deterministický konečný automat je pětice $(Q, Σ, δ, q_{0}, F)$ , kde

$Q$ je neprázdná konečná množina stavů,
$Σ$ je konečná vstupní abeceda,
$δ : Q \times Σ \to Q$ je parciální přechodová funkce,
$q_{0} \in Q$ je počáteční stav,
$F \subseteq Q$ je množina akceptujících stavů.

Rozšířená přechodová funkce $\hat{δ} : Q \times Σ^{*} \to Q$

$\hat{δ} (q, ε) = q$ pro každý stav $q \in Q$ .
$\hat{δ} (q, w a) = δ (\hat{δ} (q, w), a)$ , je-li $\hat{δ} (q, w)$ i $δ (\hat{δ} (q, w), a)$ definováno, $⊥$ jinak.

Akceptace

Slovo $w$ je akceptováno automatem $A$ , právě když $\hat{δ} (q_{0}, w) \in F$ .

Zamítání

Slovo $w$ je zamítáno automatem $A$ , právě když $\hat{δ} (q_{0}, w) \in / F$ .

Přijímaní

Jazyk přijímaný automatem $A$ je $L (A) = {w \in Σ^{*} : \hat{δ} (q_{0}, w) \in F}$ .

Ekvivalence

Automaty jsou ekvivalentní, pokud přijímají stejný jazyk.

Minimální konečný automat

Má nejmenší počet stavů a totální přechodovou funkci.

Převod na minimální konečný automat

Odstraníme nedosažitelné stavy.
Přidáme ,,peklo'' a svedeme do něj nedefinované přechody.
Rozdělíme stavy na dvě skupiny: koncové a nekoncové.
Do tabulky přechodů označíme, do které skupiny každý přechod vede.
Rozdělíme stavy do nových skupin. Ve stejné skupině budou ty stavy, u nichž se předchozí skupinové značení shoduje.
Bod 4 a 5 opakujeme, dokud lze vytvářet nové skupiny podle značení z předchozí iterace.
Výsledné skupiny tvoří nové stavy.

Převod na kanonický tvar

U automatů v kanonickém tvaru můžeme snadno srovnávat, jestli jsou stejné.

Totálně uspořádej abecedu $Σ = {a_{1}, a_{2}, ..., a_{m}}, a_{i} < a_{i + 1}$ .
Projdi automat do šířky. Následníky vol v abecedním pořadí (podle uspořádání z 1).
Časové známky vrcholů jsou nová číslas stavů.

Převod na regulární výraz

Přidej nový počáteční a koncový stav.
Odstraň zbytečné (nedosažitelné) uzly.
Uplať následující nahrazení:
- $p F q G r$ za $p F . G r$ .
- $p F q ↷^{E} G r$ za $F p F . E^{*} . G r$ .
- $p F q$ a $p G q$ za $p F + G q$ .
Opakuj 3, dokud nemáš jen počáteční a koncový stav.

Nedeterministický konečný automat (NFA)

Nedeterministický konečný automat je pětice $A = (Q, Σ, δ, q_{0}, F)$ , kde

$Q$ je neprázdná konečná množina stavů,
$Σ$ je konečná vstupní abeceda,
$δ : Q \times Σ \to 2^{Q}$ je totální přechodová funkce,
$q_{0} \in Q$ je počáteční stav,
$F \subseteq Q$ je množina akceptujících stavů.

Rozšířená přechodová funkce $\hat{δ} : Q \times Σ^{*} \to 2^{Q}$

$\hat{δ} (q, ε) = {q}$ ,
$\hat{δ} (q, w a) = ⋃_{p \in \hat{δ} (q, w)} δ (p, a)$ .

Převod na deterministický automat

Nový počáteční stav bude $r_{0} = {q_{0}}$ . Zkopíruj přechody z $q_{0}$ . $i = 0$ .
Pro dosud nezpracované $i$ a každé $a \in Σ$ , přidej nový stav $r_{i_{next}} = {q \in Q : r_{i} a q}$ . Zkopíruj přechody.
Dělej 2, dokud automat není deterministický.

DFA může být ve výsledku až exponenciálně větší.

Převod na gramatiku

Pro každý přechod $A a B$ , kde $B$ není koncový stav, přidej pravidlo $A \to a B$ .
Pro každý přechod $A a B$ , kde $B$ je koncový stav, přidej pravidlo $A \to a$ .
Pokud počáteční stav $S$ je zároveň koncový, přidej $S \to ε$ .

Regulární výrazy

Množiny regulárních výrazů nad abecedou $Σ$ je

Note	To, co je symbol regexu, je podtržené.

$\underline{ε}, \underline{\emptyset}$ a $\underline{a}$ pro každé $a \in Σ$ .
$\underline{(} E \underline{.} F \underline{)}, \underline{(} E \underline{+} F \underline{)}, \underline{(} E \underline{)^{*}}$ , pokud $E$ a $F$ jsou regulární výrazy.
nic jiného není regulární výraz.

Každý regex $E$ nad abecedou $Σ$ popisuje jazyk $L (E)$ nad stejnou abecedou:

$L (\underline{ε}) = ε$
$L (\underline{\emptyset}) = \emptyset$
$L (\underline{a}) = a$ pro každé $a \in Σ$
$L (E \underline{.} F) = L (E) . L (F)$ , kde $E$ a $F$ jsou regexy
$L (E \underline{+} F) = L (E) \cup L (F)$ , kde $E$ a $F$ jsou regexy
$L (E \underline{^{*}}) = L (E)^{*}$ , kde $E$ je regex

Regulární přechodový graf

Regulární přechodový graf je pětice $A = (Q, Σ, δ, q_{0}, F)$ , kde

$Q$ je neprázdná konečná množina stavů,
$Σ$ je konečná vstupní abeceda,
$δ : Q \times Q \to RE (Σ)$ je parciální přechodová funkce,
$q_{0} \in Q$ je počáteční stav,
$F \subseteq Q$ je množina akceptujících stavů.

Převod na NFA

Vytvoříme nový počáteční stav $q_{0}^{'}$ takový, že $q_{0}^{'} ε q_{0}$ .
Opakovaně:
- Ostraníme hrany ohodnocené $\emptyset$ .
- Nahraď $p F + G q$ za $p F q$ a $p G q$ .
- Nahraď $p F . G q$ za $p F p^{'} G q$ .
- Nahraď $p F^{*} q$ za $p ε p^{''} ↷^{F} ε q$ .

Pumping lemma pro regulární jazyky

Nechť $L$ je regulární jazyk. Pak existuje $n \in N$ takové, že libovolné slovo $w \in L$ , jehož délka je alespoň $n$ , lze psát ve tvaru $w = x . y . z$ , kde $∣ x . y ∣ \leq n, y \neq = ε$ a $x . y^{i} . z \in L$ pro každé $i \in N$ .

Myhill-Nerodova věta

Nechť $L$ je jazyk nad $Σ$ , pak následující tvrzení jsou ekvivalentní:

$L$ je rozpozntatelný konečným automatem.
$L$ je sjednoceném některých tříd rozkladu určeného pravou kongruencí na $Σ^{*}$ s konečným indexem.
Relace $\sim_{L}$ má konečný index.

Uzávěrové vlastnosti

Operace	Formulka
Sjednocení	$L_{1} \cup L_{2}$
Průnik	$L_{1} \cap L_{2}$
Rozdíl	$L_{1} ∖ L_{2}$
Doplňek	$\overline{L}$
Zřetězení	$L_{1} . L_{2}$
Iterace	$L^{*}$
Pozitivní iterace	$L^{+}$
Mocnění	$L^{n}$
Revers	$L^{R}$

Operace

Formulka

Sjednocení

$L_{1} \cup L_{2}$

Průnik

$L_{1} \cap L_{2}$

Rozdíl

$L_{1} ∖ L_{2}$

Doplňek

$\overline{L}$

Zřetězení

$L_{1} . L_{2}$

Iterace

$L^{*}$

Pozitivní iterace

$L^{+}$

Mocnění

$L^{n}$

Revers

$L^{R}$