Ciele
- Zopakovať si teóriu odvodenia konečno-stavových automatov z regulárnych výrazov.
- Precvičiť si odvodenie DKA na základe zadaného regulárneho výrazu.
- Porozumieť implementácii DKA pre daný regulárny výraz.
Úvod
Cieľom dnešného cvičenia je opakovanie a prehĺbenie teórie regulárnych výrazov a pochopenie priameho odvodenia deterministického konečno-stavového automatu z regulárneho výrazu (pomocou metódy vytvárania prechodových grafov). Ďalším cieľom je pochopenie dodanej implementácie konečno-stavového akceptora a možnosť implementácie ďalšieho akceptora.
Postup
Krok 1
Zopakujte si teóriu regulárnych výrazov. Už viete, že regulárne výrazy je možné zobraziť aj graficky pomocou prechodových diagramov. Princíp zostrojenia takýchto diagramov bol vysvetlený v predošlom cvičení.
Konečno-stavové automaty sa bežne v teórii informatiky vytvárajú prostredníctvom vytvárania prechodových tabuliek (ako je tomu v zbierke v kapitole 3.2). Takto vytvorené automaty sú nedeterministické. Nedeterministické automaty sú také, kde pri niektorom vstupe x je definovaná prechodová funkcia nie do jediného možného stavu y, ale do množiny možných stavov {y1, y2, ...yn}. Na vytvorenie deterministického automatu sa využíva metóda nazývaná determinizácia.
Na tomto predmete sa však využíva iná metóda, vytváranie prechodových grafov , ktorá je uvedená v animovanej prezentácii. Táto metóda má tú výhodu, že pomocou nej je možné vytvoriť priamo deterministický konečno-stavový automat a nie je potrebná ďalšia determinizácia. Je ju však možné použiť len vtedy, ak množinu vstupných reťazcov pre KSA je možné definovať prostredníctvom regulárnych výrazov.
Príklad
Nájdite DKA, ktorý reprezentuje regulárny výraz 0|1{0|1} (z predošlého cvičenia).
Postupovať budeme nasledujúcim spôsobom.
-
Pre daný regulárny výraz nakreslíme prechodový diagram:
Obr. 1: Prechodový diagram pre regulárny výraz 0|1{0|1} -
Určíme počiatočný stav q0 umiestnením tokenu: Stav q0 = .0|.1{0|1}
Obr. 2: Počiatočný stav -
Vygenerujeme jednotlivé stavy pomocou prechodovej funkcie δ:
-
δ(q0, 0) = q1, dostávame stav q1 = 0|1{0|1}. (koncový stav)
Obr. 3: Zmena stavu na q1 -
δ(q0, 1) = q2, dostávame stav q2 = 0|1{.0|.1}. (koncový stav)
Obr. 4: Zmena stavu na q2 -
δ(q1, 0) = ⊥, prechod nie je definovaný
-
δ(q1, 1) = ⊥, podobne ako v predošlom prípade
-
δ(q2, 0) = q2
-
δ(q2, 1) = q2
- Zostavíme tabuľku pre prechodovú funkciu:
| stav | 0 | 1 |
|---|---|---|
| q0 | q1 | q2 |
| q1 | ⊥ | ⊥ |
| q2 | q2 | q2 |
- Z prechodovej tabuľky nakreslíme DKA:
Obr. 5: DKA pre regulárny výraz 0|1{0|1}
Poznámka
Symbolom ⊥ označujeme nedefinovanú hodnotu.
Krok 2
Precvičte si vytváranie deterministického konečno-stavového akceptora na základe zadaného regulárneho výrazu s využitím metódy vytvárania prechodových grafov z predošlého kroku na nasledujúcich príkladoch:
Úloha 2.1
Vytvorte prechodový diagram regulárneho výrazu a prechodový graf. Následne vytvorený prechodový graf prekreslite na DKA.
Regulárny výraz:
a[a]{b}b
Úloha 2.2
Vytvorte prechodový diagram regulárneho výrazu a prechodový graf. Následne vytvorený prechodový graf prekreslite na DKA.
Regulárny výraz:
[c]{ab}c
Úloha 2.3
Vytvorte prechodový diagram regulárneho výrazu a prechodový graf. Následne vytvorený prechodový graf prekreslite na DKA.
Regulárny výraz:
{b}[c]ba
Úloha 2.4
Vytvorte prechodový diagram regulárneho výrazu a prechodový graf. Následne vytvorený prechodový graf prekreslite na DKA.
Regulárny výraz:
a{ab}a[ab]b
Krok 3
V prvom kroku tohto cvičenia sme sa naučili, ako priamo vytvoriť z regulárneho výrazu DKA. V tomto kroku sa oboznámime s praktickou implementáciou daného DKA v jazyku C.
Úloha 3.1
Podľa pokynov vyučujúceho samostatne implementuje DKA pre určený regulárny výraz binárnych numerálov. Zohľadnite skutočnosť, že na vstupe môže byť ľubovoľný reťazec. Váš program by mal vedieť nájsť binárne numerály v zadanom reťazci. Prediskutujte realizované riešenie.
Úloha 3.2
Podľa pokynov vyučujúceho samostatne implementuje DKA pre určený regulárny výraz z predošlého kroku. Prediskutujte realizované riešenie.
Doplňujúce úlohy
Úloha A.1
Prejdite si príklady na vytváranie regulárnych výrazov v zbierke od č. 1.13
Úloha A.2
Samostatne vyriešte príklady na vytváranie DKA v zbierke od č. 3.1 - precvičte si ich pomocou metódy vytvárania prechodových diagramov.
Úloha A.3
Precvičiť znalosti regulárnych výrazov (v ich bežnejšom zápise) môžete aj pomocou krížoviek. Skúste si niektoré regulárne výrazy z krížoviek prepísať do zápisu používaného na tomto cvičení.