Prílohy:1

Tabuľkou riadená implementácia

Z tabuľky stavov vieme univerzálnym algoritmom vyhodnotiť, či je vstup rozpoznáný automatom. Vytvoreniu tabuľky predchádza:

  • vytvorenie regulárneho výrazu,
  • prepis regulárneho výrazu do nedeterministcikého automatu,
  • úprava nedeterministického automatu na deterministický,
  • prepis deterministického automatu do tabuľky stavov.

Príklad tabuľky stavov

  pismeno cislica ine akceptuje
1 2 0 0 0
2 2 2 -3 0
3 0 0 0 1

Začiatočným stavom je stav 1. Zo vstupu postupne čítame znaky a podľa tabuľky rozhodujeme o ďalšom postupe. Vstup je rozpoznaný, ak sa dostaneme do akceptovaného stavu. Čísla v stĺpcoch pismeno, cislica a ine predstavujú číslo stavu, do ktorého vstupujeme po určení príslušného znaku. Nula je chybové hlásenie, vtedy algoritmus končí a vstup nie je rozpoznaný. Ak je číslo záporné, znamená to, že prečítaný znak budeme v ďalšom kroku čítať znovu ten istý, preto znížime index aktuálneho prvku o jedna, aby sa v ďalšom prechode opäť navýšil na tú istú hodnotu. Číslo nasledujúceho stavu získame absolútnou hodnotou.

Implementácia v Jave

public static void main(String[] args) {
        // TODO code application logic here
        
        int[][] T = {
            {2,0, 0,0},
            {2,2,-3,0},
            {0,0, 0,1}        
        };       
        
        int stav = 1; //nie nula
        String vstup = "meno=peter+4;";

        int znak;
        int i=0;
        
        /*
            -absolutnou hodnotou zistujem cislo stavu
            -prvok "-3" je namiesto "[3]"
        */
        boolean chyba=true;
        for(;;)
        {  
            if (T[stav-1][3]==1) {chyba=false; break;} //Akc
                          
            znak = vstup.charAt(i++);                       
            if (Character.isLetter(znak)) {                
                stav=Math.abs(T[stav-1][0]); //pismeno 
                if (stav==0) break;
                else if (T[stav-1][0] <0) i--; //vratenie znaku spat
            }
            else if (Character.isDigit(znak)) 
            {
                stav=Math.abs(T[stav-1][1]); //cislica                
                if (stav==0) break;
                else if (T[stav-1][1] <0) i--; //vratenie znaku spat
            }
            else {
                stav=Math.abs(T[stav-1][2]); //iny znak                
                if (stav==0) break;
                else if (T[stav-1][2] <0) i--; //vratenie znaku spat
            }  
        } 
        
        System.out.println(chyba? "chyba":"vstup vyhovuje");
    }