Daca ultima stare obtinuta $q{~k~}$ apartine {$A$}, atunci spunem ca automatul accepta stringul. Altfel spus, daca avem stringul {$s$}, {$lungime(s) = n$}, automatul accepta stringul daca si numai daca $δ( ... δ( δ(0, s{~1~}), s{~2~} ) ..., s{~n~} )$ apartine {$A$}.

Stringurile 'aa', 'aaaaaaa', 'aabababab', 'aaaba', 'ba', 'aba' sunt acceptate de automat, dar 'ba', 'abbbbbb', 'bba' nu.

Stringurile '{$aa$}', '{$aaaaaaa$}', '{$aabababab$}', '{$aaaba$}', '{$ba$}', '{$aba$}' sunt acceptate de automat, dar '{$ba$}', '{$abbbbbb$}', '{$bba$}' nu.

La ce folosesc ?

h3. La ce folosesc ?

1. Inteligenta artificiala (prima si cea mai involuata stare a inteligentei artificiale)
2. Aplicatii teoretice si probleme de matematica :)
3. Pattern matching

# Inteligenta artificiala (prima si cea mai involuata stare a inteligentei artificiale)
# Aplicatii teoretice si probleme de matematica :)
# Pattern matching

Se dau stringurile M si N. Se cere sa gasim toate aparitiile lui N in M.
Vom numi Mi prefixul lui M de lungime i. Presupunand ca avem construit automatul care accepta stringul N, vom cauta toate prefixele lui M acceptate de automat, deci toate numerele 1 <= i <= lungime(M) cu proprietatea ca automatul accepta stringul Mi.

 
 
Algoritm_potrivire_cu_automat_finit

h2. Algoritm_potrivire_cu_automat_finit

1: n = lungime(N)
2: q = 0;

Algoritm_constructie_automat_finit

h2. Algoritm_constructie_automat_finit

1: m <- lungime(M)
2: pt q <- 0, m

Acesta se poate rafina, eliminand operatii redundante, dupa cum vom vedea in cele ce urmeaza.

 
 
Algoritmul KMP

h2. Algoritmul KMP

Gaseste toate aparitiile un string N in M in timp O(n + m), unde n = lungime(N), m = lungime(M). O parte esentiala a sa este functia prefix p : {1..n} -> {0..n-1} unde p[i] = cel mai lung prefix al lui M care este sufix al lui Mi. Evident, Mp[i] (prefixul de lungime p[i] al lui M) prefix al lui Mi, deci p[i] < i.

Algoritm_calcul_functie_prefix

h3. Algoritm_calcul_functie_prefix

1: n <- lungime(N)
2: k <- 0

8: k <- k + 1
9: p[i] <- k

Analiza complexitatii :

h4. Analiza complexitatii :

- la fiecare pas (i = 2, n) k se incrementeaza cel mult o data, deci pe parcursul algoritmului k se va incrementa de cel mult n - 1 ori (linia 8)
- in linia 5, k se decrementeaza cel mult pana devine 0, deci se va decrementa de cel
mult n - 1 ori pe parcursul algoritmului

Algoritm_potrivire_KMP

h3. Algoritm_potrivire_KMP

1: m <- lungime(M), n <- lungime(N)
2: q <- 0