Ciele
- Oboznámiť sa s organizáciou cvičení predmetu Formálne jazyky a podmienkami udelenia zápočtu.
- Definovať základné pojmy teórie formálnych jazykov.
- Oboznámiť sa s regulárnymi výrazmi.
- Prakticky precvičiť zostavenie vybraných regulárnych výrazov.
Úvod
Na tomto cvičení sa oboznámite s organizáciou cvičení a podmienkami udelenia priebežného hodnotenia (zápočtu). Následne predstavíme úvod do formálnych jazykov, približíme základné pojmy, a oboznámime sa s operáciami nad jazykmi a ich abecedami. V poslednom kroku priblížime koncept regulárnych výrazov, ich konštrukcie a grafickej reprezentácie prostredníctvom prechodových diagramov. Tieto zručnosti prakticky overíme na konkrétnych príkladoch.
Postup
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, pritom 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 základných, ďalej nerozložiteľných (atomických) prvkov nazývaných symboly alebo znaky. Abecedou môže byť napríklad:
- $\{a, b, \ldots, z\}$ – abeceda pozostávajúca z malých latinských písmen,
- $\{0, 1\}$ – abeceda jazyka binárnych numerálov,
- $\{0, 1, \ldots, 9, A, B, \ldots, F\}$ – abeceda jazyka haxadecinálnych numerálov,
- $\{\mathtt{if}, \mathtt{else}, \mathtt{while}, \mathtt{if}, *, +, -, \ldots \}$ – množina lexikálnych elementov ľubovoľného programovacieho jazyka.
Poznámka
Pojem numerál označuje akýkoľvek syntaktický výraz, ktorého sémantikou (významom) je číselná hodnota.
Reťazec $w$ nad abecedou $A$ je konečná postupnosť symbolov tejto 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. $$
- Reťazce možno spájať prostredníctvom binárnej operácie zreťazenia (konkatenácie). Nech $w_1 = a_1...a_j$ a $w_2 = b_1...b_k$, kde $j,k\in\mathbb{N}_0$ 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 = w_2w_1$, je však asociatívna platí teda $(w_1w_2)w_3 = w_1(w_2w_3).$
- Ak $ w = a_1 \ldots a_n $, pre $n\in \mathbb{N}_0$, obrátený reťazec k reťazcu $w$ je reťazec
$$ w^R = a_n \ldots a_1. $$ Unárnu operáciu obrátenia (reverzácie) reťazca možno alternatívne definovať aj induktívne, čo môže byť užitočné pri dokazovaní rôznych tvrdení: $$w^R = \left\{\begin{array}{ll} \varepsilon, & \text{ak } w=\varepsilon,\\ w_r^Rx, & \text{ak } w=xw_r \text{ pre nejak}\acute{e}\text{ } x\in A\text{ a re}\check{t}\text{azec }w_r. \end{array}\color{transparent}\right\}$$
- Palindróm je reťazec pre ktorý platí:
$$ w=w^R. $$
- Ďalšou unárnou operáciou nad reťazcami je $n$-tá mocnina reťazca, kde $n\in \mathbb{N}_0$, pre ktorú platí:
$$ w^n = \underbrace{ww\ldots w}_{n\text{-}krát}.$$ Túto operáciu možno taktiež definovať induktívne, a to nasledovne: $$w^n = \left\{\begin{array}{ll} \varepsilon, & \text{ak } n=0,\\ ww^{n-1}, & \text{ak } n>0. \end{array}\color{transparent}\right\}$$ Na základe tejto definície je taktiež zrejmé, že nulta mocnina ľubovoľného reťazca je prázdny reťazec, $$w^0 = \varepsilon,$$ čo predstavuje základný prípad (z angl. base case) induktívnej definície mocniny reťazca. Keďže mocnina reťazca má vyššiu prioritu ako zreťazenie, zápis $abc^2$ reprezentuje reťazec $abcc$ a nie reťazec $abcabc$, ktoré by sme museli zapísať $(abc)^2$.
- Reťazec $w'$ nad abecedou $A$ sa nazýva:
- predpona (prefix) reťazca $w$, ak existuje taký reťazec $w_1$ nad abecedou $A$, pre ktorý platí $w=w'w_1$,
- prípona (sufix) reťazca $w$, ak existuje taký reťazec $w_1$ nad abecedou $A$, pre ktorý platí $w=w_1w'$,
- podreťazec reťazca $w$, ak existujú také reťazce $w_1$ a $w_2$ nad abecedou $A$, pre ktoré platí $w=w_1w'w_2$.
Poznámka
Prázdny reťazec je predponou, príponou a podreťazcom každého reťazca, dokonca aj prázdneho reťazca.
Príklad
Sú dané dva reťazce $w_1 = abc$ a $w_2 = abbc$.
a) Určte najmenšiu možnú (minimálnu) abecedu týchto reťazcov.
b) Určte dľžky oboch reťazcov $w_1$ a $w_2$.
c) Určte obrátený reťazec k reťazcu $w_2$.
d) Určte dĺžku reťazca $w_2 \varepsilon w_1 \varepsilon.$
e) Sú reťazce $w_2\varepsilon$ a $\varepsilon w_2$ zhodné s reťazcom $w_2$?
f) Určte reťazce $w_1^2$ a $w_2^3$.
g) Relatívne a absolútne určte reťazec, ktorý vznikne ako výsledok druhej mocniny zreťazenia nultej mocniny reťazca $w_1$ a tretej mocniny obrátenia reťazca $w_2$.
h) Ktoré reťazce sú zároveň predponou aj príponou reťazca $101110110$?
Riešenie
a) $A=\{a,b,c\}$
b) $|w_1|=3$ a $|w_2|=4$
c) $w_2^R=cbba$
d) $|w_2 \varepsilon w_1 \varepsilon| = |w_2| + |\varepsilon| + |w_1| + |\varepsilon| = 3 + 0 + 4 + 0 = 7$
e) Áno, zreťazením ľubovoľného reťazca s prázdnym reťazcom sa pôvodný reťazec nemení.
f) $w_1^2 = abcabc$ a $w_2^3 = abbcabbcabbc$
g) $(w_1^0(w_2^{R})^3)^2 = cbbacbbacbbacbbacbbacbba$
h) $\{\varepsilon, 10, 101110110\}$
Teraz pristúpime k prezentácii vzorového príkladu využitia jednej z vyššie uvedených induktívnych definícií (operácie reverzácie) pri dôkaze nasledujúceho intuitívne platného tvrdenia. Postupovať budeme metódou matematicej indukcie.
Príklad
Dokážte, že pre ľubovoľnú dvojicu reťazcov $w_1$ a $w_2$ nad abecedou $A$ platí: $(w_1w_2)^R=w_2^Rw_1^R.$
Riešenie
Pri tomto dôkaze budeme postupovať metódou matematickej indukcie vzhľadom na $|w_1|$.
- Báza
Prvým krokom dôkazu tohto tvrdenia bude dôkaz platnosti jeho špeciálneho prípadu, kedy $|w_1|=0$, a teda $w_1 = \varepsilon$. $$(w_1w_2)^R=(\varepsilon w_2)^R = w_2^R = w_2^R\varepsilon = w_2^R\varepsilon^R = \underline{\underline{w_2^Rw_1^R}}.$$ - Indukčný predpoklad (IP)
Predpokladajme, že dané tvrdenie platí pre reťazece $w_1$ dĺžky menšej alebo rovnej $n$, kde $n\in \mathbb{N}_0$. - Indukčný krok
Následne dokážeme, že dané tvrdenie platí aj pre reťazce $w_1$ dĺžky $n+1$. Predpokladajme teda reťazec $w_1=xw_r$ dĺžky $n+1$, kde $x$ je ľubovoľný symbol abecedy $A$. Je taktiež zrejmé, že $|w_r|=n$. Potom platí: $$\begin{align*} (w_1w_2)^R &= ((xw_r)w_2)^R &&\text{substit}\acute{\text{u}}\text{cia na z}\acute{\text{a}}\text{klade rovnosti }w_1=xw_r\\ &= (x(w_rw_2))^R &&\text{asociati}\text{vnos}\check{\text{t}} \text{ zre}\check{\text{t}}\text{azenia}\\ &= (w_rw_2)^Rx &&\text{z defini}\text{cie reverz}\acute{\text{a}}\text{cie}\\ &= (w_rw_2)^Rx^R &&\\ &= (w_2^Rw_r^R)x^R &&\text{aplik}\acute{\text{a}}\text{cia IP} \rightarrow\\ &= w_2^R(w_r^Rx^R) &&\text{asociati}\text{vnos}\check{\text{t}} \text{ zre}\check{\text{t}}\text{azenia}\\ &= w_2^R(xw_r)^R &&\text{aplik}\acute{\text{a}}\text{cia IP} \leftarrow\\ &= \underline{\underline{w_2^Rw_1^R}} &&\text{substit}\acute{\text{u}}\text{cia na z}\acute{\text{a}}\text{klade rovnosti }w_1=xw_r \end{align*} $$
Tvrdenie teda platí pre všetky reťazce $w_1$ a $w_2$ nad abecedou $A$. $\square$
Poznámka
$\square$ predstavuje formálne ukončenie dôkazu korešpodujúce použitiu slovenskej skratky ČBTD (čo bolo treba dokázať) alebo latinskej skratky $\mathit{QED}$ (quod erat demonstrandum).
Úloha 2.1
Dokážte tvrdenie z predchádzajuceho príkladu metódou matematickej indukcie vzhľadom na dĺžku reťazca $w_2$.
Kleeneho uzáver resp. tranzitívny uzáver $A^*$ je množina všetkých reťazcov (v rátane prázdneho reťazca $\varepsilon$) nad abecedou $A$, teda
$$ A^* = \cup_{n=0}^{\infty}A^n.$$
Pozitívny uzáver $A^+$ je množina všetkých neprázdnych reťazcov nad abecedou A, teda
$$ A^+ = \cup_{n=1}^{\infty}A^n.$$ Potom platí $$ 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^*.$$
Reťazce, ktoré patria do jazyka označujeme ako slová alebo vety jazyka.
- 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ý nasledovne: $$L^n = \left\{\begin{array}{ll} \{ \varepsilon \}, & \text{pre } n=0,\\ LL^{n-1}, & \text{pre } n>0. \end{array}\color{transparent}\right\}$$
To 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)\}.$$
Príklad
Nech je daný jazyk $ L_1 = \{ a, ab \} $ a jazyk $ L_2 = \{\varepsilon, b, ba \} $. Určte zreťazenie týchto jazykov.
Riešenie
$ L_1 L_2 = \{a\cdot\varepsilon, a\cdot b, a\cdot ba, ab\cdot \varepsilon, ab\cdot b, ab\cdot ba\}$ $= \{a, ab, aba, abb, abba \} $
Príklad
Určte prvých päť mocnín jazyka $L=\{a,ab\}$.
Riešenie
- $ L^0 = \{ \varepsilon \} $.
- $ L^1 = L \cdot L^0 : $ Zreťazujeme každé slovo jazyka $ L $ s každým slovom jazyka $ L^0 $ $$ L^1 = \{ a \cdot \varepsilon, ab \cdot \varepsilon \} = \{ a, ab \}. $$
- $ L^2 = L \cdot L^1 : $ Zreťazujeme každé slovo jazyka $ L $ s každým slovom jazyka $ L^1 $ $$ L^2 = \{ a \cdot a, a \cdot ab, ab \cdot a, ab \cdot ab \} = \{ aa, aab, aba, abab \}. $$
- $ L^3 = L \cdot L^2 : $ Zreťazujeme každé slovo jazyka $ L $ s každým slovom jazyka $ L^2 $ $$ L^3 = \{ aaa, aaab, aaba, aabab, abaa, abaab, ababa, ababab \}. $$
- $ L^4 = L \cdot L^3 : $ Zreťazujeme každé slovo jazyka $ L $ s každým slovom jazyka $ L^3 $ $$ L^4 = \{ aaaa, aaaab, aaaba, aaabab, aabaa, aabaab, aababa, aababab, abaaa, abaaab,$$ $$abaaba, abaabab, ababaa, ababaab, abababa, abababab\}. $$
Príklad
Nech sú dané jazyky $L_1=\{baaab, aba, aaa, bbb\}$ a $L_2=\{a\}$. Určte ľavý kvocient jazyka $L_1$ podľa jazyka $L_2$
Riešenie
Keďže jazyk $L_2$ obsahuje len jeden prvok $a$, v jazyku $L_1$ nás budú zaujímať len reťazce s predponou $a$, teda reťazce: $\textcolor{red}{a}ba,\textcolor{red}{a}aa$. Výsledok určime tak, že z týchto reťazcov odtrhneme predponu $\textcolor{red}{a}.$ $L_2\backslash L_1=\{ba,aa\}$
Úloha 2.2
Nech $ L = \{ \varepsilon, a \} $. Určte prvky jazyka $L^3$, dľžku najdlhšieho reťazca tohto jazyka a počet prvkov.
Úloha 2.3
Predpokladajme $ w = xy+ $ . Utvorte zreťazenie reťazca $w$ a druhej mocniny obráteného reťazca $w$.
Úloha 2.4
Kedy je iterácia $L^*$ jazyka $L$ konečným jazykom?
Úloha 2.5
Nech sú dané jazyky $ L_1 = \{ aa, ab, ba, bb \}, L_2 = \{ a, b \}. $ Určte prienik jazyka $L_1$ a druhej mocniny jazyka $L_2$.
Úloha 2.6
Nech $A$ je ľubovoľná abeceda. Určte prvky jazyka $A^* – A^+$ a počet prvkov tohto jazyka.
Úloha 2.7
Určte mohutnosť (počet reťazcov) ľavého kvocientu ľubovoľného jazyka $L$ podľa jazyka $\{\varepsilon\}.$
Úloha 2.8
Predpokladajme reťazec $w$ dĺžky $n$ nad ľubovoľnou abecedou $A$. Aká je početnosť jazyka definovaného ako množiny všetkých predpôn reťazca $w$.
Keďže formálny jazyk je definovaný ako ľubovoľná podmnožina množiny všetkých reťazcov nad danou 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 (extenzionálny spôsob) a
- určením jeho charakteristickej vlastnosti (intenzionálny spôsob).
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.
Príklad
Určte jazyk $L$ nad abecedou $A=\{a\}$, ktorý pozostáva len z reťazcov tvorených párnym počtom za sebou nasledujúcich výskytov symbolu $a$ a určte všetky prvky tohto jazyka pre ktoré platí $|w|\leq 5$.
Riešenie
$L = \{a^{n}\;|\;n\in \mathbb{N}_0 \land 2\mid n\}$
Prvky jazyka $L$ pre ktoré platí $|w|\leq 5$ sú $\varepsilon, aa, aaaa$.
V rámci tohto predmetu sa však prioritne budeme zaoberať precíznejšími (pokročilými) spôsobmi špecifikácie jazykov, a to:
- inštanciovaním prostredníctvom regulárnych výrazov,
- akceptovaním prostredníctvom automatov, a
- generovaním prostredníctvom formálnych gramatík.
Krok 3
Regulárne výrazy predstavujú stručný formalizmus na opis tzv. regulárnych jazykov definovaný americkým matematikom a logikom Stephenom Coleom Kleenem. Samotný princíp určenia jazyka pomocou regulárneho výrazu spočíva v špecifikácii vzoru, ktorý splňajú všetky slová tohto jazyka, ktoré preto možno označiť za konkrétne inštancie tohto vzoru.
Nasledujúca induktívna definícia sytematicky opisuje postup konštrukcie týchto vzorov z najjednoduchších atomických častí postupným skladaním.
Medzi atomické (elementárne) tvary regulárnych výrazov patria:
- $\varepsilon$ – regulárny výraz označujúci jazyk pozostávajúci z jediného reťazca $\varepsilon$,
- $a$, pre $a\in A$, kde $A$ je abeceda daného regulárneho jazyka – regulárny výraz označujúci jazyk pozostávajúci z jediného reťazca $a$.
Následne možno pristúpiť k vymenovaniu zložených tvarov regulárnych výrazov. Nech $R$, $R_1$ a $R_2$ sú reguárne výrazy označujúce jazyky $L$, $L_1$ a $L_2$. Potom
- ${R}_1{R}_2$ zreťazenie je regulárny výraz označujúci jazyk $L_1L_2$, napr. regulárny výraz $ab$ identifikuje jazyk pozostávajúci z jediného reťazca $ab$,
- ${R}_1|{R}_2$ alternácia je regulárny výraz označujúci jazyk $L_1\cup L_2$, napr. regulárny výraz $a|b$ identifikuje jazyk pozostávajúci z reťazcov $a$,$b$,
- $\{R\}$ Kleeneho uzáver je regulárny výraz označujúci jazyk $L^*$, napr. regulárny výraz $\{a\}$ identifikuje jazyk pozostávajúci z reťazcov $\varepsilon$, $a$, $aa$, $aaa, \ldots$,
- $R\{R\}$ pozitívny uzáver je regulárny výraz označujúci jazyk $L^+$, napr. regulárny výraz $a\{a\}$ identifikuje jazyk pozostávajúci z reťazcov $a$, $aa$, $aaa, \ldots$
- $[R]$ voliteľnosť je regulárny výraz označujúci jazyk $L\cup\{\varepsilon\}$, napr. regulárny výraz $[a]$ identifikuje jazyk pozostávajúci z reťazcov $\varepsilon$, $a$.
Upozornenie
V regulárnych výrazoch sa termín alternácia používa na označenie operátora výberu, kým termín alternatíva označuje jednotlivé operandy tohto operátora.
Poznámka
Zreťazenie má vyššiu prioritu ako alternácia. Z tohto dôvodu je regulárny výraz $ab|c\{d\}$ ekvivalentný regulárnemu výrazu $(ab)|(c\{d\})$ a nie výrazu $a(b|c)\{d\}$.
Okrem vyššie prezentovanej teoretickej notácie zápisu regulárnych výrazov sa možno v programátorskej praxi často stretnúť s inou notáciu ich zápisu. V nasledujúcej tabuľke porovnávame tieto dva základné notačné štandardy využívaných na tomto predmete. Zatiaľ čo prvý z nich sa využíva skôr v akadenickom prostredí a pedagogickom procese s druhým sa je možné najčastejšie stretnúť v existujúcich implementáciách regulárnych výrazov (napr. v programovacích jazykoch, ako Python, C atď.).
| Tvar regulárneho výrazu | Zjednodušený zápis (používaný na tomto predmete) | Zápis bežný v implementáciách | |
|---|---|---|---|
| Prázdny reťazec | $\varepsilon$ | ||
| Symbol | $a$ | $a$ | |
| Zreťazenie (sekvencia) | ${R}_1{R}_2$ | ${R}_1{R}_2$ | |
| Alternácia (výber) | ${R}_1|{R}_2$ | ${R}_1|{R}_2$ | |
| Kleeneho uzáver (iterácia) | $\{R\}$ | $R*$ | |
| Pozitívny uzáver (pozitívna iterácia) | $R\{R\}$ | $R+$ | |
| Voliteľnosť | $[R]$ | $R?$ |
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$.
Poznámka
Skráteny zápis pre skupinu znakov, ako napríklad $0-9$, je skratkou zápisu $0|1|3|4|5|6|7|8|9$.
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.
Poznámka
V nasledujúcich schémach sú elementárne uzly prechodových diagramov znázornené krúžkami, zatiaľ čo poddiagramy, využívané pri konštrukcii diagramov zložených regulárnych výrazov, sú znázornené štvorcami. Toto rozlíšenie vyplýva z induktívnej povahy definície regulárnych výrazov
Príklad
Skonštruujte prechodový diagram pre regulárny výraz binárnych numerálov (reťazcov reprezentujúcich binárne čísla).
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. 3. 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.
Príklad
Skonštruujte prechodové diagramy pre regulárne výrazy $ab|c\{d\}$ a $a(b|c)\{d\}$.
Riešenie
$ab|c\{d\}$
$a(b|c)\{d\}$
Krok 4
Úloha 4.1
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov $a$ a $b$, ktorý obsahuje podreťazec $abba$.
Úloha 4.2
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov $x$ a $y$, v ktorých je každý výskyt znaku $y$ bezprostredne nasledovaný postupnosťou troch znakov $x$.
Úloha 4.3
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov $p$ a $q$, ktoré obsahujú nepárny počet znakov $q$.
Úloha 4.4
Skonštruujte regulárny výraz pre overenie zápisu identifikátora.
Zápis identifikátora má nasledujúce vlastnosti:
- identifikátor môže (a nemusí) začínať znakom $,
- následne prvý znak môže byť len malé alebo veľké písmeno latinskej abecedy,
- ďalšie znaky (ak sa v pomenovaní vyskytujú) môžu tvoriť ľubovoľnú kombináciu malých alebo veľkých písmen latinskej abecedy alebo ľubovoľné číslice.
Úloha 4.5
Skonštruujte regulárny výraz pre overenie zápisu rodného čísla (podľa slovenskej legislatívy).
V zápise rodného čísla:
- sa môže vyskytovať oddeľovač '/', prípadne zápis neobsahuje žiaden oddeľovač,
- skupina číslic za oddeľovačom môže mať dĺžku tri alebo štyri znaky,
- pri mesiacoch sa vyskytujú dve možné postupnosti: $01-12$, $51-62$.
Úloha 4.6
Skonštruujte regulárny výraz pre overenie zápisu reálneho čísla.
Zápis čísla má nasledujúce vlastnosti:
- číslo môže byť kladné alebo záporné,
- číslo môže a nemusí obsahovať desatinnú časť,
- číslo musí mať vyjadrenú celú časť na aspoň jednu platnú číslicu,
- ak číslo obsahuje aj desatinnú časť, aj tá musí byť vyjadrená na aspoň jednu platnú číslicu,
- oddeľovač celej a desatinnej časti môže byť znak desatinnej čiarky ',' alebo desatinnej bodky '.'
Ako zabezpečíte, aby numerál neobsahoval nevýznamné nuly zľava? Prečo musíme pri celej aj desatinnej časti čísla uvažovať aspoň jednu platnú číslicu?
Úloha 4.7
Zostrojte prechodové diagramy pre regulárne výrazy z predchádzajúcich úloh.
Doplňujúce zdroje
Vizualizačné nástroje znázorňujúce proces rozpoznávania textu na základe regulárnych výrazov využívajúce znázornenie na ich prechodových diagramoch.
Poznámka
Všetky nástroje používajú alternatívny bežný zápis regulárnych výrazov, s ktorým ste sa oboznámili na tomto cvičení. Pred použitím oboch vizualizačných nástrojov odporúčame dôkladne sa oboznámiť so vstupným tvarom regulárnych výrazov, ktoré obidva nástroje používajú.
Dotazník na ohodnotenie učiva
Vážení študenti,
týmto by sme Vás chceli požiadať o poskytnutie spätnej väzby k formátu a obsahu materiálov na cvičenia vo forme vyplnenie nasledujúceho dotazníka .
Tento dotazník slúži na ohodnotenie vašich skúseností s pripravenými materiálmi z prvého cvičenia. Na vylepšovaní materiálov na základe vašej spätnej väzby aktívne pracujeme, a to s cieľom zvýšiť kvalitu, zrozumiteľnosť a prínosnosť výučby.