Úvod do formálnych jazykov. Operácie nad jazykmi a ich abecedami. Úvod do regulárnych výrazov.

Krok 1

Oboznámte sa s organizáciou cvičení predmetu Formálne jazyky a podmienkami udelenia zápočtu.

Krok 2

Jazyk je základným komunikačným prostriedkom nie len v interpersonálnej komunikácii ale taktiež pri komunikácii človeka s výpočtovým systémom. V prípade druhej z vyššie uvedených situácií však nemožno predpokladať realizáciu komunikácie v tak syntakticky a sémanticky voľnej forme, ako poskytujú práve prirodzené jazyky, čo podnietilo vznik počítačových (formálnych) jazykov a intenzívny výskum v tejto oblasti.

Štandardne rozoznávame tri základné roviny jazyka:

• syntaktickú,
• sémantickú a
• fonetickú.

Keďže fonetická rovina je vlastná iba prirodzeným jazykom, pri štúdiu formálnych jazykov sa možno uberať dvoma smermi. Americký lingvista Noam Chomsky, jedna z najvýznamnejších postáv tejto výskumnej oblasti, výrazne prispel k všeobecne prijatej idei primátu syntaxe. Na tomto základe sa dnes pod pojmom teória formálnych jazykov rozumie výlučne štúdium ich syntaktických zákonitostí.

Teraz sa zoznámime so základnými pojmami teórie formálnych jazykov:

Abeceda $A$ je konečná neprázdna množina prvkov nazývaných symboly. Abecedou môže byť napríklad:

• $\{a, b, \ldots, z\}$ – abeceda pozostávajúca z malých latinských písmen,
• $\{0, 1\}$ – abeceda binárnych čísel,
• $\{0, 1, \ldots, 9, A, B, \ldots, F\}$ – abeceda haxadecinálnych čísel,
• $\{\mathtt{if}, \mathtt{else}, \mathtt{while}, \mathtt{if}, *, +, -, \ldots \}$ – množina lexikálnych elementov programovacieho jazyka.

Reťazec $w$ nad abecedou $A$, taktiež označovaný ako slovo resp. veta je ľubovoľná postupnosť symbolov $A$.

• Počet symbolov v reťazci $w$ nazývame dĺžkou reťazca a označujeme $|w|$
• Špeciálny prípad reťazca je tzv. prázdny reťazec označovaný $\varepsilon$, pre ktorého dĺžku platí:

$$ |\varepsilon| = 0. $$

• Ak $ w = a_1 \ldots a_n $ je reťazec nad abecedou $A$, potom obrátený reťazec k reťazcu $w$ je reťazec

$$ w^R = a_n \ldots a_1. $$

• Reťazce možno spájať prostredníctvom binárnej operácie zreťazenia. Nech $w_1 = a_1...a_j$ a $w_2 = b_1...b_k$ sú reťazce nad abecedou A. Potom zreťazenie reťazcov $w_1$ a $w_2$ je reťazec $w_1\cdot w_2$ (alebo skrátene $w_1w_2$), pre ktorý platí:

$$ w_1 w_2 = a_1 \ldots a_j b_1 \ldots b_k .$$ Operácia zreťazenia nie je komutatívna t. j. neplatí $w_1w_2 \neq w_2w_1$.

• Ďalšou v tomto prípade však unárnou operáciou nad reťazcami je $n$-tá mocnina reťazca $w^n$. Ak $w$ je reťazec a $n\in \mathbb{N}_0$, potom reťazec

$$ w^n = \underbrace{ww\ldots w}_{n\text{-}krát},$$ je reťazec, ktorý vznikne zreťazením $n$ kópií reťazca $w$. Keďže mocnina reťazca má vyššiu prioritu ako zreťazenie slovo $abc^2$ predstavuje slovo $abcc$, a nie slovo $abcabc$, to by sme museli zapísať $(abc)^2$. Nultá mocnina ľubovoľného reťazca je prázdny reťazec, $$w^0 = \varepsilon.$$

• Ak $w_1, w_2, w_3$ sú tri reťazce, potom $w_1$ je predponou (prefix), $w_2$ je podreťazcom a $w_3$ je príponou (sufix) reťazca $w_1w_2w_3$.

Kleeneho uzáver resp. tranzitívny uzáver $A^*$ je množina všetkých reťazcov nad abecedou $A$. Pozitívny uzáver $A^+$ je množina všetkých neprázdnych reťazcov nad abecedou A. Platí teda

$$ A^+ = A^* - \{\varepsilon\}.$$

Formálny jazyk $L$ je ľubovoľná podmnožina množiny všetkých možných reťazcov nad abecedou tohto jazyka $A$,

$$L \subseteq A^*.$$

• Nech $L_1$, $L_2$ sú jazyky. Potom zreťazením týchto jazykov nazývame jazyk

$$ L_1 \cdot L_2 = \{ w_1w_2\;|\; w_1 \in L_1 \land w_2 \in L_2 \}. $$

• Nech L je jazyk. Potom jeho $n$-tou mocninou $L^n$ (pre $n\in\mathbb{N}_0$) nazývame jazyk definovaný takto:

$$ L^0 = \{ \varepsilon \}, \text{ pre } n=0$$ $$ L^{n} = L \cdot L^{n-1}, \text{ pre } n>0$$ čo znamená, že jazyk $ L^{n} $ sa skladá zo všetkých reťazcov, ktoré vzniknú zreťazením reťazcov jazyka $L$ s reťazcami jazyka $ L^{n-1}$.

• Iterácia (Kleeneho uzáver) jazyka $L$ je jazyk $L^*$, ktorý vznikne zjednotením všetkých celých nezáporných mocnín jazyka $L$,

$$L^*=\cup_{n=0}^{\infty}L^n.$$

• Pozitívny iterácia (Kleeneho pozitívny uzáver) jazyka $L$ je jazyk $L^+$, ktorý vznikne zjednotením všetkých prirodzených mocnín jazyka $L$,

$$L^+=\cup_{n=1}^{\infty}L^n.$$

• Nech $L_1$, $L_2$ sú jazyky. Ich zjednotením je jazyk, ktorý obsahuje všetky reťazce z $L_1​$ a všetky reťazce z $L_2$​,

$$L_1 \cup L_2 = \{w \;|\; w\in L_1 \lor w\in L_2\}.$$​

• Nech $L_1$, $L_2$ sú jazyky. Ich prienikom je jazyk, ktorý obsahuje len tie reťazce, ktoré sú súčasne v $L_1$​ aj $L_2$​,

$$L_1\cap L_2=\{w \;|\; w\in L_1 \land w\in L_2\}.$$

• Nech $L_1$, $L_2$ sú jazyky. Ich rozdielom je jazyk, ktorý obsahuje tie reťazce z $L_1$​, ktoré nie sú v $L_2$.

$$L_1−L_2=\{w \;|\; w\in L_1 \land w\not\in L_2\}.$$

• Nech $L$ je jazyk nad abecedou $A$. Potom jeho doplnkom resp. komplementom $L^C$ nazývame jazyk, ktorý obsahuje všetky reťazce nad abecedou $A$, ktoré nepatria do $L$,

$$ L^C = A^* - L.$$

• Nech $L_1$, $L_2$ sú jazyky. Ľavý kvocient jazyka $L_1$ podľa $L_2$ je jazyk, pre ktorý platí:

$$L_2\backslash L_1=\{w_1\;|\;(\exists w_2 \in L_2)(w_2w_1\in L_1)\}$$

Keďže formálny jazyk je definovaný ako množina reťazocov nad určitou abecedou $A$, všimnime si, že základné (primitívne) spôsoby jeho určenia korešpondujú so základnými spôsobmi úrčenia množiny, a to konkrétne:

• vymenovaným všetkých prvkov a
• určením jeho charakteristickej vlastnosti.

Zatiaľ čo prvý spôsob možno uplatniť len v prípade konečných jazykov, druhý spôsob umožňuje jednoznačne určiť aj nekonečné jazyky, čo ukážeme na nasledujúcom príklade.

V rámci tohto predmetu sa však prioritne budeme zaoberať precíznejšími spôsobmi definície jazykov, z ktorých prvým sú regulárne výrazy.

Krok 3

Regulárne výrazy sú základným pojmom v teoretickej informatike a poskytujú stručný formalizmus na opis tzv. regulárnych jazykov, o ktorých si neskôr povieme viac.

Zopakujte si teóriu regulárnych výrazov.

Regulárne výrazy sa môžu zapisovať rôznymi spôsobmi. V tabuľke je v druhom stĺpci uvedený zjednodušený zápis, ktorý sa používa na tomto predmete. V treťom stĺpci je uvedený zápis, s ktorým sa najčastejšie môžete stretnúť v existujúcich implementáciách regulárnych výrazov. Väčšina zápisov regulárnych výrazov tiež ponúka viaceré skrátené zápisy pre celé skupiny znakov, ako napríklad cifry 0-9 či malé a veľké písmená latinskej abecedy a-z a A-Z.

Teraz si bližme popíšme nasledujúce elementárne (atomické) tvary regulárnych výrazov:

• ε je regulárny výraz identifikujúci množinu reťazcov pozostávajúcu z jediného reťazca $\varepsilon$,
• a, pre $a\in T$ je regulárny výraz identifikujúci množinu reťazcov pozostávajúcu z jediného reťazca zodpovedajúceho $a$.

Následne možno pristúpiť k opisu zložených (molekulárnych) tvarov regulárnych zýrazov. Nech R, R${}_1$ a R${}_2$ sú reguárne výrazy identifikujúce jazyky $L$, $L_1$ a $L_2$. Potom

• R${}_1$R${}_2$ je regulárny výraz identifikujúci jazyk $L_1\cdot L_2$, napríklad regulárny výraz ab identifikuje jazyk pozostávajúci z jediného reťazca $ab$,
• R${}_1$|R${}_2$ je regulárny výraz identifikujúci jazyk $L_1\cup L_2$, napríklad regulárny výraz a|b identifikuje jazyk pozostávajúci z reťazcov $a$,$b$,
• {R} je regulárny výraz identifikujúci jazyk $L^*$, napríklad regulárny výraz {a} identifikuje jazyk pozostávajúci z reťazcov $\varepsilon$, $a$, $aa$, $aaa, \ldots$,
• R{R} je regulárny výraz identifikujúci jazyk $L^+$, napríklad regulárny výraz a{a} identifikuje jazyk pozostávajúci z reťazcov $a$, $aa$, $aaa, \ldots$
• [R] je regulárny výraz identifikujúci jazyk $L\cup\{\varepsilon\}$, napríklad regulárny výraz [a] identifikuje jazyk pozostávajúci z reťazcov $\varepsilon$, $a$.

Regulárne výrazy je možné zobraziť aj graficky pomocou prechodových diagramov. Princíp zostrojenia takéhoto diagramu je znázornený na nasledujúcom obrázku.

Riešenie

0|1{0|1}
Pre zostrojenie prechodového diagramu je doležite postupovať krok za krokom.
Tento výraz nám alternatíva delí na 2 časti: 0 a 1{0|1}
Začneme zobrazením $0$.

Ďalej je na rade alternatíva začínajúca symbolom $1$.

Teraz prichádza na radu tranzitívny uzáver v ktorom sa nachádza alternatíva. Najprv zobrazíme symbol $0$.

Následne k tranzitívnemu uzáveru pripojíme $1$, ktorá nenasléduje za $0$ ale musí byť zobrazená tak by bolo možné prejsť cez $0$ alebo $1$.

Máme zostrojený prechodový diagram.
Identifikovať jednotlivé tvary, ktoré predstavujú konkrétne inštancie tohto regulárneho výrazu (vzoru) je možné postupným prechodom týmto diagram.
Možme začať tým, že prejdeme prvú časť diagramu, kde je možné identifikovať iba symbol $0$ zo vstupného reťazca Prechádzaním druhej časti môžme zisiť, že je možné identifikovať symbol $1$ alebo prechádzaním tranzitívneho uzáveru vieme identifikovaž zložené tvary (ako sú napr. $10$, $11$, $100$, $101$). Na základe čoho je možné tento regulárny výraz považovať za definíciu jazyka binárnych numerálov $0$, $1$, $10$, $11$, $100$, $101$, $110$, $111\ldots$

Riešenie

ab|c{d}

a(b|c){d}

Krok 4