Resultats de la cerca
Es mostren 3 resultats
autòmat finit indeterminista
Matemàtiques
Estructura de la forma M = (Q, ∑, δ, I, F) on Q és un conjunt finit no buit, els elements del qual s’anomenen estats; ∑ és un alfabet anomenat d’entrada; δ : 2Q ⨉ ∑* → 2Q és la funció de transició que satisfà ∀P1, P2 ⊂ Q, ∀x, y∈∑*: δ(∅, x) = ∅, δ(P1, λ) = P1, δ(P1 ∪ P2, x) = δ(P1, x) ∪ δ(P2, x), δ(P1, xy) = δ(δ(P1, x)y), essent xy la concatenació de x i de y i ∑* el conjunt de paraules; I ⊂ Q és el conjunt d’estats inicial; F ⊂ Q és el conjunt d’estats finals o acceptadors.
Usualment un autòmat finit indeterminista es descriu mitjançant el seu diagrama de transicions Es tracta d’un graf dirigit que té els estats per vèrtex si un arc que va de q i a q j amb etiqueta a si q j ∈ δ q i , a S’indiquen els esstats inicials amb fletxes i els finals amb una creu Els llenguatges acceptats pels autòmats finits indeterministes són els mateixos que els reconeguts pels finits deterministes regulars L’avantatge dels indeterministes enfront dels deterministes és la facilitat de maneig i de construcció
topologia
© Fototeca.cat
Matemàtiques
Part de la matemàtica que estudia aquelles propietats dels conjunts de punts de la recta, del pla, de l’espai o d’espais de dimensions superiors que no són alterades per les transformacions contínues.
Es tracta de propietats geomètriques que no depenen de cap magnitud, sinó únicament de la posició relativa dels punts Per exemple, el fet que dos punts puguin unir-se o no per un camí, o que el nombre de cares menys el d’arestes més el de vèrtexs d’un políedre esfèric sigui sempre dos teorema d’Euler Aquí hom entén per transformació contínua aquella que admet una inversa i que tant ella com la inversa són contínues L’íntima connexió que hi ha entre el concepte de continuïtat d’una funció en un punt i el d’entorn d’un punt permet de transportar l’estudi de propietats topològiques a aquells…
arbre
© fototeca.cat
Matemàtiques
Graf connex i acíclic (sense circuits).
Un arbre té només un vèrtex, anomenat arrel sense predecessor en el sentit de les fletxes, mentre que tot altre vèrtex té, cada un, un únic predecessor Tots els vèrtexs tenen un nombre variable de successors, que ordinariàment hom suposa ordenats per exemple, d’esquerra a dreta i de vegades són anomenats branques En la representació habitual d’un arbre l’arrel se situa al capdamunt i els arcs se suposen recorreguts en sentit descendent Els arbres han passat d’ésser un cas particular de graf a rebre un tractament matemàtic específic Són particularment útils en la modelització de…