Sfida nga Pr-Tech: Përpuethshmëria e vargjeve

[edspace]

Sfida është hapur nga Grupi Teknologjik i Prishtinës. Po e hedhim në forum që anëtarët të mund të diskutojnë zgjidhjet dhe të mësojnë nga eksperienca e njëri-tjetrit. Tema do qëndrojë e mbyllur gjatë kohës që sfida është e hapur dhe zgjidhja juaj nuk duhet bërë publike gjatë kësaj kohe. Kur të skadojë afati i lejuar, tema do hapet dhe pastaj mund të postoni përgjigjet tuaja dhe të diskutoni me anëtarët e tjerë.

Gjetja e përpuethshmërisë në mes të vargut dhe mostrës
Krijuar/Përpiluar nga: Genc DOKO - gdk ET pr-tech PIKË net
Problemi eshte i hapur
Prej:14/02/2005 Deri:28/02/2005

Këtë herë ju jeni të sfiduar me krijimin e një programi i cili do t'a merr një varg dhe një mostër dhe do të gjen përputshmërinë ndërmjet këtyre dyjave. Vargu përbëhet prej çfarëdo shkronje (përveç simbolit "*"). Ndërsa mostra mund të përmbajë çfarëdo shkronje, duke e përfshirë edhe simbolin "*" i cili e luan rolin e "xhol-it", d.m.th. ai mund të përfaqësojë 0 apo më shumë shkronja të ndryshme apo të njejta.

Për t'i kuptuar kërkesat e kësaj sfide, shifni rastet e mëposhtme:

gjeje ("abcdef", "*abcdef"); // saktë
gjeje ("abcdef", "*abcdef*"); // saktë
gjeje ("abcdef", "abcdef*"); // saktë
gjeje ("abcdef", "a*");    // saktë
gjeje ("abcdef", "*b*");   // saktë
gjeje ("abcdef", "*bd");   // pasaktë
gjeje ("abcdef", "*f");    // saktë
gjeje ("abcdef", "*bcd*");  // saktë
gjeje ("abcdef", "ab*ef");  // saktë
gjeje ("abcdef", "a*f");   // saktë
gjeje ("abcdef", "*");    // saktë
gjeje ("abcdef", "bcd");   // pasaktë
gjeje ("abcdef", "abcde");  // pasaktë
gjeje ("abcdef", "bcdef");  // pasaktë
gjeje ("abcdef", "abc*def"); // saktë

Të jeni në dijeni që "regular expressions" të Perl-it apo cfarëdo funksione të ngjajshme nuk lejohen pasi që e tërë esenca është të zhvillohet algoritmi.

Mënyra për I/O varret nga preferenca e koduesit. Programi mundet të shkruhet në C, C++, Java, Visual Basic (ose VB .NET), C#. Nëse programi juaj përmbanë më shumë se një skedar atëherë le të arkivohet si tar.gz apo zip dhe si i tillë le të dërgohet në programim ET pr-tech PIKË net.

[edspace]

Zgjidhja që është programuar më poshtë, merr vargun dhe mostrën si argumenta. Variablat vpoz dhe mpoz përdoren si indekse për përputhjen e vargjeve. Fillojnë tek zero dhe rriten për çdo copë të mostrës që përputhet me vargun, deri sa arrijnë në fund.

// Programi: Sfida e Javes nga Grupi Teknologjik i Prishtines 
//           Gjetja e perpuethshmerise ne mes te vargut dhe mostres
// Data: 28/02/05 
// Perpiluesi: Dev-C++ 4.9.9.2 
// Pershkrimi: Kontrollon nese mostra perputhet me vargun
//             Vargu eshte tekst i thjeshte ndersa mostra mund te kete 
//             germa magjike (ose xhola). Xholi eshte ylli "*"
// Perdorimi: programi "vargu" "most*ra" 
// Shembuj: "Shqiptar" "Shqiptar" = sakte
//          "Forumi Shqiptar" "* Shqiptar" = sakte
//          "Prishtina Tech" "Prisht* T*" = sakte
//          "Tirana" "T****" = sakte
//          "Tirana" "*T****" = sakte
//          "Tirana" "*a" = gabim sepse kap "a"-ne e pare 
//          "Tirana" "*a*n" = sakte sepse kap "a"-ne e pare 

#include <iostream>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    if( argc != 3 )  // nqs nuk kemi argumentat e sakte
    {
        cerr << "GABIM: Mungon vargu ose mostra." << endl;
        cout << "Shembull: gjej \"vargu\" \"*mos*tra*\"" << endl;
        return EXIT_FAILURE;  
    }
    
    string v = argv[1]; // v = vargu
    string m = argv[2]; // m = mostra
    string::size_type vpoz = 0; // pozicioni i vargut
    string::size_type mpoz = 0; // pozicioni i mostres
    string mcop = "";  // perdoret per te copetuar mostren cope*cope2*cope3
    
    bool sakte = true; // supozojme se mostra = vargun
    bool xhol = false; // perdoret per te ruajtur xholin -> *

    while( sakte && mpoz < m.size() )  // cikel per aq kohe sa nuk kemi gabim
    {                                  // dhe nuk kemi arritur fundin e mostres
        if( m[mpoz] == '*' )           // nqs gjejme nje xhol
        {
            xhol = true;               // e mbajme mend
            mpoz++;                    // vazhdojme me shkronjen tjeter
            if( mpoz == m.length() )   // nqs xholi eshte ne fund te vargut
            { 
                vpoz = v.length();     // vargu eshte automatikisht i sakte
            }
        }
        
        string::size_type xhpoz = m.find("*", mpoz); // gjejme xholin tjeter
        
        if( xhpoz == string::npos )    // nqs nuk kemi xhol
        {
            xhpoz = m.size();          // pozicioni i xholit eshte fundi
        }
        
        // marrim copen e mostres te ndare nga xholat. Psh: "Shqip*tar"
        // mcop = Shqip
        mcop = m.substr(mpoz, xhpoz - mpoz ); 
        
        // kerkojme mostren ne varg
        string::size_type vpoz2 = v.find(mcop, vpoz);
        
        if( vpoz2 == string::npos ) // nqs mostra nuk gjendet ne varg
        {
            sakte = false; // gabim
        }
        else if( xhol ) // nqs gjendet dhe kemi xhol
        {               // psh: "Shqiptar" "*tar"
            xhol = false; // heqim xholin
            vpoz = vpoz2 + mcop.length(); // vazhdojme tek copa tjeter e vargut
            mpoz = mpoz + mcop.length();  // vazhdojme tek copa tjeter e mostres
        }
        else if( vpoz == vpoz2 ) // nqs nuk kemi xhol por mostra gjendet ne varg
        {                        // psh: "Shqiptar" "Shqip"
            vpoz = vpoz + mcop.length(); // vazhdojme tek copa tjeter e vargut
            mpoz = mpoz + mcop.length(); // vazhdojme tek copa tjeter e mostres
        }
        else // nqs gjejme mostren por nuk kemi xhol
        {    // psh: "Shqiptar" "tar" 
            sakte = false;  // gabim
        }
    }
    
    if( sakte && vpoz == v.length() )  // vpoz == v.length eshte per rastet
    {                                  // qe mostra eshte pjese e vargut
        cout << "sakte" << endl;       // psh: "Shqiptar" "Shqip"  => gabim
    }
    else
    {
        cout << "gabim" << endl;
    }
    
    return EXIT_SUCCESS;
} 

[edspace]

sfida.h

/* Programues :   Josif Grabocka 
< e140862 ET metu PIKË edu.tr  >

* Emri i Programit:  Kontrolli i 'wild char-s', (perfshi '?') */

int gjeje(char * model, char * varg){

  int l_m=strlen(model), l_s=strlen(varg), i_m=0, i_s=0, k=0;
    
  for( ; (i_s < l_s) && (i_m < l_m) ; i_s++)
    if( varg[i_s]!='*' && varg[i_s]!='?' ){
      if(varg[i_s]==model[i_m]) i_m++;
      else return 0;
    }
    else if( varg[i_s]=='*' ) {
      for(k=i_m ; k<l_m ; k++)
        if(model[i_m++]==varg[i_s+1]) break;
      i_m=k;
    }
    else if( varg[i_s]=='?' ) { if(model[i_m++ + 1] != varg[i_s + 1]) return 0; }
        
return i_m != l_m ? 0 : 1;
} 

Programi Kryesor:

#include <stdio.h>
#include <string.h>

#include "sfida.h"

int main(void){

  printf("\nSakte=1 Gabim=0\n\n");
  
  printf("%d\n",  gjeje("abcdef", "?b*f") );  /* sakte */
  printf("%d\n",  gjeje("abcdef", "?b*d*f") ); /* sakte */
  printf("%d\n",  gjeje("abcdef", "?b*df") ); /* gabim */  
  printf("%d\n",  gjeje("abcdef", "?b?d?f") ); /* sakte */
  printf("%d\n",  gjeje("abcdef", "ab?cdef") );/* gabim */
  printf("%d\n\n", gjeje("abcdef", "*c?e*") ); /* sakte */

return 0;
} 

[edspace]

Kjo eshte zgjidhja e vete autorit te sfides.

/*
** Description: Finding the pattern within a given string.
** Author: Genc Doko <gdk ET pr-tech PIKË net>.
** Date: 14 February, 2005.
*/

#include <stdio.h>
#include <string.h>

int match (char s[], char p[]);

int main(){
 
 char string[64];
 char pattern[64];
 
 gets (string);
 gets (pattern);
 
 if (strlen(pattern) > strlen(string)){
  if ((pattern[0] != '*') && (pattern[strlen(pattern)-1] != '*')){
   printf ("Pattern can't be greater than string!\n");
   return 0;
  }
 }
 
 if (match (string, pattern))
  printf ("Match!\n");
 else
  printf ("Don't match!\n");
 
 return 0;
}

int match (char s[], char p[]){
 
 char *stringPointer;
 char *patternPointer;
 
 stringPointer = &s[0];
 patternPointer = &p[0];
 
 while (1){
  
  if (*patternPointer == '*')
   goto skip;
  
  if (*stringPointer == '\0')
   return 1;
  
  if (*stringPointer == *patternPointer){
   stringPointer++;
   patternPointer++;
   continue;
  }
  
  if (*stringPointer != *patternPointer)
   return 0;
  
 skip:
  patternPointer++;
  if (*patternPointer == '\0')
   return 1;
  
  for (;;stringPointer++){
   
   if (*stringPointer == *patternPointer){
  stringPointer++;
  patternPointer++;
  break;
   }
   
   if (*stringPointer == '\0')
  return 0;
  }
 }
} 

[edspace]

Që të treja zgjidhjet më lart janë të ngjashme. E mira e C++ është se mund të përdorësh funksione të gatshme të klasës String (basic_string), që është pjesë e librarive standarde. Funksionet më të përdorur janë find() dhe substr().

Psh:

string varg = "Shqiptar";
string::size_type poz = varg.find("Shqip"); // kërkojmë fjalën Shqip në Shqiptar
if( poz != string::npos )
{
     cout << "Shqip u gjend ne pozicionin" << poz;
}
else
{
     cout << "Shqip nuk u gjend";
} 

Kodi më lart do nxjerrë në ekran: "Shqip u gjend ne pozicionin 0".
0 1 2 3 4 5 6 7
S H Q I P T A R

Mos harroni se numërimi i gërmave fillon nga zero, prandaj duhet treguar kujdes kur përdoren funksionet find, substr, etj.

string::size_type është një tip i veçantë i klasës string i cili përdoret si indeks për gërmat e një vargu. Mund të përdoret edhe tipi int por size_type është ndërtuar kastile për këtë punë, prandaj sugjerohet që të mos përdoret int.

string::npos është një vlerë konstante e klasës String që tregon një pozicion të pavlefshëm të vargut. Në int ajo ka vlerën -1 sepse vargu nuk ka asnjë gërmë me këtë vlerë. Funksion find përgjigjet me npos nëse mostra që ne kërkojmë nuk gjendet në varg, prandaj sa herë që përdoret find() duhet të ketë edhe një kusht që shikon nëse përgjigja është e barabartë me string::npos.

Substr() është shkurtim i Sub-String që përkthehet nën-varg ose një copë e vargut. Funksioni përdoret për të marrë vetëm një pjesë të vargut duke i dhënë pozicionin e nisjes dhe numrin e shkronjave që duam.
psh:

string kombesia = "Shqiptar"
string gjuha = varg.substr(0, 5); //fillojme tek 0 dhe marrim 5 shkronja 

Nga kodi më lart, vargu gjuha = "Shqip".

C-ja ka funksione për vargjet por nuk janë aq të avancuar sa ato të C++, prandaj shpeshherë programuesit e C duhet të punojnë me gërmat një nga një.

Më vonë mund të shkruaj diçka më shumë, por kush ka pyetje, le ti bëjë.

[IlirDeda]

Me duket se si Genci ashtu edhe Josifi kane bere te njejtin gabim.
P.sh. aaaaaaua dhe a*aua perputhen, por te dy programet thone qe nuk perputhen.
Nderkohe programi i Edit jep pergjigjen e sakte.

[IlirDeda]

Ketu me poshte eshte edhe programi im.
Eshte i shkruar ne C# dhe besoj se eshte nje ilustrim i mire per Object-Oriented programming.
Eshte interesante se ua kisha derguar atyre te Pr-Tech (nepermjet nje forme ne Website), por nuk e kane publikuar. Mbase ajo forma nuk punon.

//Ky program eshte ne C#. 
//Metoda e perdorur per zgjidhjen eshte NFA (Nondeterministic Finite Automata)
//Ruaje si skedar nfa.cs
//Kompiloje me komanden: csc nfa.cs
//Zbatoje: nfa.exe
//Autor Ilir Deda, 27 Shkurt 2005

using System;

abstract class State {
    public abstract bool check(String str);

    public void addState(State st) {
        if(Next == null) {
            Next = st;
        } else {
            Next.addState(st);
        }    
    }    
    
    protected State Next {
        get {
            return next;
        }    
        set {
            next = value;
        }    
    }        
    private State next = null;
};

class CharState : State {
    public override bool check(String str) {
        if(str.Length==0) {
            return false;
        }
        if(str[0]==transition) {
            return Next.check(str.Substring(1));
        } else {
            return false;
        }
    }
    
    public CharState(char transition) {
        this.transition = transition;
    }    
    private char transition;
};

class StarState : State {
    public override bool check(String str) {
        bool result = Next.check(str);
        if(str.Length==0) {
            return result;
        } else {         
            return result || check(str.Substring(1));
        }    
    }
};

class FinalState : State {
    public override bool check(String str) {
        if(str.Length == 0) {
            return true;
        } else {
            return false;
        }  
    }     
};

class Nfa {
    public Nfa(String str) {
        int i = 0;
        State newState = null;
        while(i < str.Length) {
            if(str[i] != '*') {
                newState = new CharState(str[i]);
            } else {
                newState = new StarState();
            }    
            if(firstState==null) {
                firstState = newState;
            } else {
                firstState.addState(newState);
            }
            i++;
        }
        if(firstState!=null) {
            firstState.addState(new FinalState());
        }    
    }

    public bool check(String str) {
        if(firstState != null) {
            return firstState.check(str);
        } else {
            return false;
        }    
    }    
    
    private State firstState = null;
};    

public class MainClass {

    static void gjeje(string varg, string moster) {
        Nfa nfa = new Nfa(moster);
        Console.Write("gjeje (\"{0}\", \"{1}\");   //", varg, moster); 
        if(nfa.check(varg)) {
            Console.WriteLine("saktë");
        } else { 
            Console.WriteLine("pasaktë");
        }
    }    
    public static void Main() {
        gjeje ("abcdef", "*abcdef"); // saktë
        gjeje ("abcdef", "*abcdef*"); // saktë
        gjeje ("abcdef", "abcdef*"); // saktë
        gjeje ("abcdef", "a*");    // saktë
        gjeje ("abcdef", "*b*");   // saktë
        gjeje ("abcdef", "*bd");   // pasaktë
        gjeje ("abcdef", "*f");    // saktë
        gjeje ("abcdef", "*bcd*");  // saktë
        gjeje ("abcdef", "ab*ef");  // saktë
        gjeje ("abcdef", "a*f");   // saktë
        gjeje ("abcdef", "*");    // saktë
        gjeje ("abcdef", "bcd");   // pasaktë
        gjeje ("abcdef", "abcde");  // pasaktë
        gjeje ("abcdef", "bcdef");  // pasaktë
        gjeje ("abcdef", "abc*def"); // saktë
        gjeje ("aaaaef", "a*aef"); // saktë
    }
}; 

[edspace]

Gabime të tjera të programit të Josifit dhe Gencit.

Në atë të Gencit:
abc abc*** = Nuk përputhet
aaaaaha a*aaha = Nuk përputhet (ajo që përmëndi dhe Iliri më lart)
abc a*b*c = Mostra nuk mund të jetë më e gjatë se vargu.

Në atë të Josifit:
abc abcd = përputhet
aaaaaha a*aaha = nuk përputhet

[edspace]

Ilir,

Interesante metoda që ke përdorur. Po të kesh kohë, a mund të shkruash më shumë për NFA dhe të vendosësh ca komente për kodin. Kam lexuar pak për NFA por nuk kam njohuri për CSharp.

Programin tënd e testova dhe nuk gjeta ndonjë gabim. Në fakt më bëri përshtypje se programi përfshin edhe përputhjen lakmitare (greedy).
psh:
1. Tirana *a = sakte
2. Tirana *a*na = sakte

Në rastin e parë, xholi lakmon për "Tiran" ndërsa në rastin e dytë lakmon vetëm për "Tir".
Sfida nuk kishte përcaktuar rregull për lakminë, prandaj në programin tim nuk e përdora atë. Në RegEx të Perl mbaj mend që ka mënyra për të caktuar nëse është lakmitar apo jo.

Çfarë ndodh në programin tënd që i kap të dyja rastet?

[IlirDeda]

Edi, faleminderit per ftesen per te shkruar per NFA Une po shpresoja per rezultatin e kundert, d.m.th. qe njerezit te shihnin programin tim dhe te frymezoheshin te lexonin ndonje liber per kete teme.
Librat qe mund te konsultohen per Finite Automata jane librat e "Theory of Computation" ose librat e teorise se kompilatoreve. Ne keta te fundit mund te gjendet edhe kod.
Eshte teper e veshtire te shkruash per Finite Automata, aq me teper ne nje Web page pasi duhen vizatuar diagrama. Ndoshta ne te ardhmen mund ta bej nje gje te tille por kjo kerkon pune te madhe.
Megjithate po them dy fjale megjithese kam frike qe me shume do ngaterroj se do sqaroj.
Ne nje Finite Automata (FA) kemi gjendje (states) dhe kalime (transitions). Nga nje gjendje ne nje tjeter kalohet npermjet kalimeve. Njera nga gjendjet eshte gjendja fillestare (start state). Ekzistojne gjithashtu nje ose me shume gjendje pranuese (accepting states).
Pjese perberese e nje FA eshte edhe alfabeti. P.sh. nje alfabet mund te jete {a,b}. Ne rastin e problemit tone alfabet eshte çdo char i gjuhes se programimit te perdorur.
Cdo kalim eshte i percaktuar nga nje germe e alfabetit ose nga epsilon (bosh).
Nje kalim mund te coje nga nje gjendje ne tjeter por mund edhe te te coje ne te njejten gjendje. Kalimi bosh do te thote qe mund te kalosh nga nje gjendje ne tjetren pa pare asnje germe te alfabetit.
Nje string eshte nje renditje e germave te alfabetit.
Nje FA mund ta pranoje nje string ose mund te mos e pranoje. Procesi i verifikimt behet ne kete menyre:
Fillohet nga gjendja fillestare. Per cdo germe nga string shihet kalimi. Nese nje kalim ekziston atehere vazhdohet. Nese nuk ekziston kalimi perkates stringu nuk pranohet. Stringu pranohet nese pasi jane harxhuar te gjitha germat e stringut kemi arritur nje nje gjendje pranuese.

Kemi dy lloj FA: NFA (Nondeterministic FA) dhe DFA (Deterministic FA). Ndryshimi qendron qe ne nje DFA nuk kemi kalime boshe dhe per nje germe te alfabetit kemi e shumta nje kalim qe niset nga nje gjendje e caktuar (d.m.th. e njejta germe nuk mund te te coje ne dy gjendje te ndryshme njekohesisht).
Nga perkufizimi duket sikur DFA jane me te thjeshta. Konceptet qe shoqerohen me NFA (kalime boshe, nje germe te con njekohesisht ne dy gjendje) duken pak si te nderlikuara ne nje shikim te pare.
Dy FA jane ekuivalente kur pranojne te njejten bashkesi stringjesh. Per cdo NFA mund te ndertohet DFA ekuivalente (ekziston algoritmi). Ne pergjithesi DFA do kete me shume gjendje se NFA. Teorikisht nese n eshte numri i gjendjeve te nje NFA, numri i gjendjeve te DFA ekuivalente mund te jete 2^n. Ne praktike numri i gjendjeve te DFA ekuivalante nuk eshte shume me i madh se numri i gjendjeve te NFA.
Disa DFA mund te jene ekuivalente me njera-tjetren. DFA minimale quhet DFA qe ka numrin me te vogel te gjendjeve. Ekzistojne algoritme per te gjetur DFA minimale te nje DFA te dhene.

Tani te pjesa interesante.
Çdo regular expression ka NFA e vet ekuivalente. Ndertimi i NFA duke u nisur nga nje regular expression behet sipas nje algoritmi te thjeshte.
Nese dikush ka perdorur Lex ose Flex e di se c'eshte nje Skaner (Scanner). Lex nuk ben gje tjeter vecse merr disa regular expressions qe percaktojne tokens per nje gjuhe te caktuar dhe gjeneron DFA perkatese qe mund te perdoret per te njohur stringjet e gjuhes.
Vini re qe une thashe gjeneron DFA. Kjo behet sepse megjithese gjenerimi i NFA eshte fare i thjeshte, perdorimi i NFA ben qe algoritmi i njohjes te ece shume ngadale (teorikisht mund te jete eksponencial). Prandaj Lex fillimisht gjeneron nje NFA dhe pastaj e kthen kete ne nje DFA te cilin pastaj mund ta kompilojme ne nje program C dhe ta zbatojme (Lex kryen edhe disa funksione te tjera te cilat ndihmojne per shkrimin e kompilatoreve. Nder keto me i rendesishmi eshte ai qe i tregon parserit se cili eshte token-i i rradhes).

Vijme ne rastin tone konkret. Problemi yne nuk kerkon njohjen e nje regular expression te pergjithshem. Ne rastin tone kemi vetem karaktere te zakonshme nga alfabeti (a, b, c etj., por jo *) si dhe * (yll). Yll do te thote qe 0 ose me shume karaktere nga stringu mund te perdoren per te bere match.
Une vendosa te perdor NFA pasi jane shume me te thjeshte se DFA. Kjo do te thote qe programi im eshte me i ngadalshem se nje program optimal, por ne rastin tone kjo nuk perben ndonje problem.
Per cdo karakter te regular expression une gjeneroj nje gjendje. Une vendosa qe gjendja do te perfaqesoje edhe kalimin qe te nxjerr nga ajo gjendje. Prandaj kemi CharState d.m.th. qe kalimi nga kjo gjendje behet me nje karakter te thjeshte dhe StarState d.m.th. qe kalimi behet me metoden yll. Me keto krijohet nje NFA. Meqe kemi vetem CharState dhe StarState NFA mund te perfaqesohet nga nje liste lineare (Ne rastin e pergjithshem do ishte graf). Nuk kemi nevoje per Start State sepse NFA eshte vete Start State. Nderkohe qe gjendja e fundit e NFA eshte nje gjendje speciale qe e kam quajtur FinalState por qe ne fakt eshte nje Accepting State.
Algoritmi per krijimin e NFA eshte teper i thjeshte. Analizohet regular expression karakter per karakter. Nese shihet nje * krijohet nje StartState dhe shtohet ne fund te listes. Nese shihet nje karakter tjeter, krijohet nje CharState dhe shtohet ne fund te listes. Pasi te kete mbaruar se analizuari regular expression shtohet edhe nje FinalState ne fund.

Algoritmi per te bere njohjen (matching, check) te nje stringu punon keshtu:
Fillohet nga karakteri i pare deri tek i fundit (Te gjithe karakteret analizohen, te pakten nje here). Karakteri i pare i kalohet gjendjes se pare. Nese kjo gjendje eshte CharState shihet kalimi i kesaj gjendje. Nese kalimi ka te njejtin karakter si karakteri i stringut atehere vazhdohet me tej. Perndryshe nuk mund te vazhdohet me tej dhe kthehet false.
Nese gjendja eshte StarState, atehere kalohet menjehere ne gjendjen pasardhese (kalim bosh). Nese gjendja pasardhese kthen true atehere edhe ne kthejme true. Nese gjendja pasardhese kthen false atehere bejme nje kalim ne te njeten gjendje duke harxhuar nje karakter (mos harro se jemi yll) dhe pastaj provohet kalimi bosh ne gjendjen pasardhese. Vazhdojme keshtu derisa gjendja pasardhese na kthen true ose derisa te harxhohen te gjitha karakteret e stringut. Ne kete rastin e fundit kthejme false natyrisht. Verej qe gjendja pasardhese mund te ktheje true vetem nese eshte FinalState dhe s'ka mbetur me asnje karakter per tu analizuar, ose nese jane ndjekur te gjitha gjendjet pas saj eshte arritur ne nje FinalState dhe s'ka mbetur me asnje karakter per tu analizuar.
Kaq ka algoritmi. I vetmi sqarim qe mund te shtoj eshte qe funksioni check() ne gjendjen StarState eshte funksion rekursiv. Si i tille ai ben backtracking automatikisht sa here qe hyn ne rruge te gabuar.
P.sh shih rastin e krahasimit te aaaaef me a*aef.
NFA eshte i tille
(1) CharState(a) ->
(2) StarState ->
(3) CharState(a) ->
(4) CharState(e) ->
(5) CharState(f) ->
(6) FinalState
Fillojme krahasimin e stringut.
Ne gjendjen (1) kemi a pra kalojme.
Ne gjendjen (2) provojme kalimin bosh.
Ne gjendjen (3) kemi a pra kalojme
Ne gjendjen (4) kemi a pra nuk kalojme
Kthehemi ne gjendjen (3)
Kthehemi ne gjendjen (2)
Ne gjendjen (2) hame nje karakter (a e dyte) dhe rrime prape ne (2)
Ne gjendjen (2) provojme kalimim bosh
Ne gjendjen (3) kemi a pra kalojme
Ne gjendjen (4) kemi a pra nuk kalojme
Kthehemi ne gjendjen (3)
Kthehemi ne gjendjen (2)
Ne gjendjen (2) hame nje karakter (a e trete) dhe rrime prape ne (2)
Ne gjendjen (2) provojme kalimim bosh
Ne gjendjen (3) kemi a pra kalojme
Ne gjendjen (4) kemi e pra nuk kalojme
Ne gjendjen (5) kemi f pra nuk kalojme
Ne gjendjen (6) Stringu ka mbaruar. Gjendja eshte pranuese pra pranojme.
NFA pranon.

Une besoj se algoritmi i Gencit dhe i Josifit nuk bejne backtraking prandaj edhe deshtojne ne kete test.
Fakti qe algoritmi i Edit nuk deshton ne kete rast, deshmon vetem per zgjuarsine e tij, pasi edhe ai nuk ben backtracking. Por nese algoritmi sajohet vete siç ka bere ai eshte e mundur te gjenden raste qe Edi nuk i ka paramenduar, sic ishte rasti qe gjeti vete ai.
Ndersa nese gjenden raste per te cilat programi im jep pergjigje te gabuar kjo do te thote qe une kam bere ndonje gabim programimi pasi algoritmet jane studiuar per 40 vjet nga mijera shkencetare dhe nuk ka se si te jene te gabuara.

Fakti qe programi eshte shkruar ne C# nuk do te thote asgje. Edhe ne Java ose ne C++ programi do dukeshe pothuajse njelloj. I vetmi funksion i C#, qe nuk e ka Java, qe kam perdorur une eshte properties (Get, Set), por keto jane vetem per paraqitje te jashtme. Ne Java do shkruheshe p.sh. GetNext(), SetNext().

Duke e mbyllur uroj qe ti kem zgjuar ndonjerit deshiren qe te mesoje me shume per Finite Automata.