Automate finite

[•GooDy]

Ce este un automat??? Si cum se realizeaza urmatoarele aplicati? :


# Construirea unui automat

# Simplificare de automate

# Echivalenta de automate

Va multumesc anticipat.

[•amadaeus]

Termenul se refera la automate finite (finite automata). Pentru detalii vezi articolul lui Adrian Vladu de aici si prezentarea introductiva de aici.

Cat despre algoritmii de simplificare sau echivalenta, poti gasi cateva paper-uri pe net, insa cred ca sunt destul de avansati pentru inceputuri. Sunt multe altele de invatat pana la automate finite 

[•GooDy]

Deci stai sa vad daca am inteles bine.
"Automate finite" se foloseste pentru verificarea de cate ori apare un subsir intr-un sir?

da in cazul acesta modul cel mai rapid nu ar fi folosind strcmp ??

[•GooDy]

Pai de exemplu urmatorul program:

Cod:

#include <iostream.h>
#include <fstream.h>
#include <string.h>

ifstream f("date.in");
ofstream g("date.out");

const long max = 10000;
char a[max],b[max],*p=b;

int n,m;

void main()
{
f.getline(a,max);
f.getline(b,max);
n=strlen(a);
m=strlen(b);
int i,nr=0,c[1000];
float ok;
for(i=1;(i<=m-n+1)&&(nr<1000);i++)
	{
	if (strncmp(a,p,n)==0)
		{
		nr++;
		c[nr]=i-1;
		}
	p++;
	}
g<<nr<<endl;
for(i=1;i<=nr;i++)
	g<<c[i]<<" ";
}

[•amadaeus]

Un automat finit poate fi folosit si pentru string matching. Odata construit automatul pentru un anumit pattern, toate aparitiile acestui pattern intr-un sir pot fi gasite in timp proportional cu lungimea sirului - complexitate O(N).

Nu stiu exact cum este implementat intern strcmp, insa banuiesc ca nu are la baza un algoritm liniar, prin urmare pentru siruri si patternuri de lungimi mari nu se va comporta la fel de bine ca un algoritm performant de potrivire, cum ar fi KMP (Knuth-Morris-Pratt), Rabin-Karp sau Boyer-Moore.

[•Cosmin]

Ai aici 4 sau 5 slideuri care explica sumar ce se intampla la echivalenta si la minimizare, dar cred ca sunt de ajuns ca sa iti faci o idee.

http://www.cag.lcs.mit.edu/6.004/Lectures/lect6/sld012.htm

Stiu ca s-a dat la lot prin 2000 sau 2001 minimizare de automat si echivalenta de automate la un concurs ACM si cateva de la topcoder. Si era la ONI 2006 o discutie prin comisie despre minimizarea automatelor.

[•devilkind]

@cosmin: m-am uitat pe slideul ala pe care l-ai pus insa nu am inteles cum pot sa verific in timp polinomial daca 2 stari sunt echivalente (daca pot).

[•Cosmin]

Ok hai ca intru in detalii:

Ai doua noduri a, b ele nu sunt echivalente daca exista un sir S astfel ca trecand prin sirul S pornind de la a ajungi la o stare finala si pornind de la nodul b ajungi la o stare ce nu e finala. (sau invers de la b ajungi la stare finala si de la a nu)

Ca sa vezi daca le poti diferentia poti face un graf in care nodurile grafului sunt perechi de stari din automatul initial, iar muchia etichetata cu 0 de la nodul (a,b) merge in nodul (d(a, 0), d(b, 0)). Acum ca sa vezi daca (a, b) sunt echivalente faci un DFS din nodul (a, b) si vezi daca poti atinge un nod in acest graf care sa fie o pereche de stare finala si stare nefinala in automatul initial.

Prin metoda asta poti vedea daca doua automate sunt echivalente, doar faci un DFS din starile de start ale celor doua automate.

Poti sa il folosesti si pentru simplificare, dar s-ar putea sa iti iasa complexitatea O(n^4).


Algoritmul de minimizare care imi placea mie pornea de la clase mari care erau cat de cat echivalente. Intai pornesti de la doua clase, cea a nodurilor finale si cea a nodurilor nefinale. Si apoi tot rafinezi clasele. Daca ai doua elemente in o clasa care indica spre elemente din clase diferite, e clar ca trebuie sa spargi clasa in doua. Asa ajungi sa obtii un algoritm de complexitate O(n^2).

[•amadaeus]

Am gasit cateva paper-uri in care este explicata constructia unui "minimal acyclic deterministic finite automata" (de exemplu acesta), in care se prezinta constructia unui automat care poate accepta un dictionar de cuvinte. Metoda e destul de simpla, se porneste de la "reversed trie" (trie-ul cuvintelor inversate) si se inverseaza si acesta, eliminand apoi starile sau lanturile care se regasesc in alte lanturi.

Totusi, un astfel de automat poate accepta orice cuvant dintr-o anumita multime de cuvinte, nu poate fi folosit insa pentru string matching. De exemplu, un automat de potrivire pentru un singur pattern P trebuie sa accepte orice cuvant x astfel incat P este sufix al lui x. Similar, un automat de potrivire pentru a gasi toate aparitiile pattern-urilor P1 si P2 ar insemna sa accepte orice cuvant x astfel incat P1 este sufix al lui x sau P2 este sufix al lui x etc.

Intrebarea mea era legata de constructia automatelor pentru potrivirile "multi-pattern" - se poate asa ceva in timp polinomial (banuiesc ca da), si cum anume?

Am crezut acum cateva zile ca am reusit sa gasesc un algoritm in O(L*|sigma|), unde L este lungimea totala a pattern-urilor, se pare insa ca nu functioneaza asa cum ma asteptam

[•Cosmin]

Lucian ce vrei tu (automat folosit pentru string matching care accepta o multime de cuvinte date) se face cu algoritmul Aho Corasik, e intr-o anumita masura similar cu KMP doar ca in loc sa faci un automat pe un sir pentru un singur string faci un trie pentru mai multe stringuri. Vezi aici o explicatie http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf .

Trieul obtinut din algoritmul respectiv te ajuta sa rezolvi si alte probleme care nu au neaparat legatura cu string matching, cum ar fi determinarea numarului de cuvinte de lungime n ce nu contin ca subsecventa nici un cuvant din o multime S data.

[•amadaeus]

Multumesc, Cosmin! E exact ce cautam 

[•Cosmin]

Ar fi misto ca franturile astea de informatii de pe forum sa fie adunate in niste articole. Am mai adaugat la infoarena.ro/training-path linkuri si probleme pe care le-am parcurs de-a lungul timpului, dar nu mai am timp liber sa le transform in articole.

[•amadaeus]

Cred ca daca se va pastra sistemul prezent de wiki, baza educationala infoarena va creste considerabil. Training-path-ul e extraordinar, si eu sper ca fiecare element al listelor de acolo sa se transforme in articole de sine statatoare. Mai aveam de anul trecut niste proiecte de articole, care au ramas insa la faza de ciorne, tot din lipsa timpului; dupa ONI insa, o sa scriu eu despre Aho-Corasick, am citit acum si ideea mi se pare super.

[•Cosmin]

Misto sa imi zici cand incepi sa scrii daca ai nevoie de materiale, ca stiam mai multe probleme ce se rezolvau cu trucul asta dar trebuie sa le adun.

[•devilkind]

stiam mai multe probleme ce se rezolvau cu trucul asta dar trebuie sa le adun.

http://infoarena.ro/problema/abc2
http://acm.timus.ru/problem.aspx?space=1&num=1158

[•Prostu]

Lucrarea mea de atestat este despre automate finite. Nu este foarte riguroasa, nici nu are prea multe desene, deci nu stiu cat de bine ce se intelege ce am scris. Majoritatea informatiilor sunt luate din Introducere in Algoritmi de Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest si Efficient Algorithms on Texts de M. Crochemore, W. Rytter.
Daca e cineva curios ce am inteles eu din automate finite, poate downloada pdf-ul de aici: http://infoarena.ro/utilizator/prostu?action=download&file=atestat.pdf

[•GooDy]

Dankeeeeee, intr-un final am reusit sa inteleg si eu ce e cu automatele

10x :*

[•amadaeus]

Imi place proiectul Din cate vad, varianta optimizata a constructiei automatului folosind functia prefix urmareste aceeasi idee din algoritmul Aho-Corasick, in care ei calculeaza o functie "fail" pentru fiecare nod din trie.

O obiectie, totusi, la reprezentarea grafica a trie-ului, din primul exemplu: din cate stiam, un trie ar trebui sa aiba muchiile etichetate cu caractere din sigma, iar tu ai etichetat nodurile; oricum, ideea de baza se pastreaza, insa pentru consistenta definitiei pe care ai enuntat-o si tu in lucrare cu cateva randuri inainte, ma gandesc ca un exemplu ar fi trebuit sa arate in genul asta http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png 

[•Cosmin]

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1620

Cartea lui Rytter http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html

Probleme cu automate pe topcoder

http://www.google.com/search?hl=en&q=automaton+site%3Awww.topcoder.com%2Ftc&btnG=Search

http://www.google.com/search?hl=en&q=automata+site%3Awww.topcoder.com%2Ftc&btnG=Search

[•Prostu]

O obiectie, totusi, la reprezentarea grafica a trie-ului, din primul exemplu: din cate stiam, un trie ar trebui sa aiba muchiile etichetate cu caractere din sigma, iar tu ai etichetat nodurile; oricum, ideea de baza se pastreaza, insa pentru consistenta definitiei pe care ai enuntat-o si tu in lucrare cu cateva randuri inainte, ma gandesc ca un exemplu ar fi trebuit sa arate in genul asta http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png 

Ai dreptate, insa m-am multumit la momentul respectiv cu acel exemplu, pentru ca este foarte aproape de modul in care implementezi trie-ul.

[•flmanea]

Un document gasit pe net cu minimizarea automatelor (inclusiv algoritmul de minimizare in O(QV log Q)): http://funinf.cs.unibuc.ro/~flmanea/Hopcroft.pdf
Prezentarea care am facut-o la lot in 2006: http://funinf.cs.unibuc.ro/~flmanea/prezentareLot.pdf

[•Cosmin]

Florine vad ca nu faci echivalenta de automate cu un dfs pe QxQ. Mie metoda cu dfs imi place cel mai mult.

[•flmanea]

Lucrarea mea de atestat este despre automate finite. Nu este foarte riguroasa, nici nu are prea multe desene, deci nu stiu cat de bine ce se intelege ce am scris. Majoritatea informatiilor sunt luate din Introducere in Algoritmi de Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest si Efficient Algorithms on Texts de M. Crochemore, W. Rytter.
Daca e cineva curios ce am inteles eu din automate finite, poate downloada pdf-ul de aici: http://infoarena.ro/utilizator/prostu?action=download&file=atestat.pdf

Pare misto lucrarea ta de atestat Felicitari! Am mai pus aici cateva carti care sunt de folos cand vrei sa inveti teoria automatelor sau limbaje formale: http://flmanea.blogspot.com/2008/03/influent-computer-science-books.html (sunt bune si cele cu titlul legat de complexitate, au capitole de teoria automatelor, din care poti afla exact ce e necesar in studiul teoriei complexitatii)

[•flmanea]

Florine vad ca nu faci echivalenta de automate cu un dfs pe QxQ. Mie metoda cu dfs imi place cel mai mult.

In prezentarea aia era o varianta care folosea minimizarea... ca aplicatie la minimizare. Oricum, daca faci cu minimizare in QV log Q obtii un timp mai bun, nu?

[•Cosmin]

de obicei lumea nu stie sa faca minimizare in q^2 si tu vrei in q log q. Nu e frumos . Mai bine incepem cu inceputul. Si apoi ridicam standardele. M-am uitat prin prezentare si ma gandeam ca ar fi misto daca ai avea ceva notite mai detaliate, poate de la cursurile tale. Pt ca desi contin multe chestii interesante sunt scrise pe slideuri doar formulele si nu e usor inteligibil pt cineva care chiar vrea sa studieze chestiile alea.