Ú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 nielen 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. To 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á len prirodzeným jazykom, pri štúdiu formálnych jazykov sa možno uberať dvoma smermi, a to štúdiom ich syntaxe alebo sémantiky. Americký lingvista Noam Chomsky, jedna z najvýznamnejších osobností tejto výskumnej oblasti, výrazne prispel k všeobecne prijatej idei primátu syntaxe. Na tomto základe sa dnes preto pod pojmom teórie 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 jednoduchého programovacieho jazyka.

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

• 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$ tak predstavuje slovo $abcc$ a nie slovo $abcabc$, ktoré by sme museli zapísať $(abc)^2$. Nultá mocnina ľubovoľného reťazca je prázdny reťazec, $$w^0 = \varepsilon,$$ čo je špecifický prípad mocniny reťazca.

• 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ívna iterácia 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$, 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 v 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 v druhom stĺpci uvádzame zjednodušený zápis, ktorý sa používa v tomto predmete. V treťom stĺpci je uvedený zápis, s ktorým sa najčastejšie môžeme 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.

Regulárne výrazy možu mať atomický alebo zložený tvar. Atomické (elementárne) tvary regulárnych výrazov sú nasledujúce:

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

Následne možno pristúpiť k vymenovaniu zložených 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}
Začíname konštrukciou prechodových diagramov elementárnych regulárnych výrazov, z ktorých sa daný regulárny výraz skladá. Následne aplikujeme kompozičné pravidla z Obr. 2. za účelom konštrukcie prechodových diagramov zodpovedajúcich jednotlivým zloženým tvarom regulárnych výrazov až pokiaľ nezískane výsledný prechodový diagram.

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 diagramom. Môžeme 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