Une FSA peut-elle compter?

11

Cela peut être une question stupide. Il semble clair qu'une FSA, étant finie, ne peut compter que le nombre de symboles dans sa chaîne d'entrée jusqu'à un nombre limité par le nombre de ses états. Mais supposons maintenant que nous équipons le FSA de capacités de sortie (par exemple, d'impression). Il serait alors très facile de construire une machine capable d'imprimer un symbole pour chaque symbole lu. Est-ce que cela compterait pour compter? Sinon, pourquoi pas?

Pour le dire en termes de FST à la place: je suppose qu'il n'est pas possible de construire un FST capable de mapper une chaîne d'une longueur arbitraire à une représentation binaire (c'est-à-dire un nombre dans le système numérique de base 2) de sa longueur. Mais il est bien sûr trivial de construire un FST capable de mapper une chaîne de longueur arbitraire à une chaîne dedits zéros (ou uns) de même longueur. Mais cela pourrait compter comme comptage, n'est-ce pas, parce que ce que fait le FST est de construire une représentation de la longueur de son entrée. Une représentation un peu étrange, mais toujours une représentation, n'est-ce pas?

automata finite-automata Torbjörn
la source

1

Donc vous posez vraiment la question "qu'est-ce qui compte?" Pour moi, cela ne ressemble pas à de l'informatique. Ce serait de l'informatique si votre question était "pour cette définition du comptage, une FSA peut-elle compter?".

Sasho Nikolov

8

Cette question est un peu vague, alors voici une réponse vague: Traduire unaire en unaire ne compte pas exactement, car la machine ne "sait" pas réellement quelle était la taille de l'entrée "à la fin".

Vous vous en rendez compte, bien sûr, c'est pourquoi vous remettez en question le fait que cela compte effectivement.

Cependant, la traduction d'unaire en binaire semble être une opération beaucoup plus avancée, car elle n'implique pas seulement le comptage, elle implique également l'arithmétique.

Alors peut-être la notion la plus précise à regarder, au lieu de compter, est de comparer . Autrement dit, étant donné deux nombres (en unaire) et , déterminez si . $1^n$ $1^m$ $n=m$

La capacité de faire cette comparaison est à l'origine de la fameuse langue non régulière . Et l'incapacité d'une NFA à compter est ce qui rend cette langue non régulière. $\{a^nb^n: n\ge 0\}$

Fait intéressant, cette langue est une LFC. Et en effet, le modèle d'automates correspondant - PDA, a la capacité de faire une comparaison limitée.

Lorsque vous parlez de comparer, les transducteurs ne vous donnent plus de puissance supplémentaire, donc la question est résolue dans ce sens.

Une note supplémentaire: de manière tout à fait informelle, la possibilité de comparer deux nombres peut souvent être utilisée pour simuler une machine Minsky à 2 compteurs , qui sont équivalentes aux MT.

Shaull
la source

4

Non. Les automates à états finis ne comptent pas. Ils peuvent faire des choses qui leur ressemblent, mais ils ne peuvent pas compter. Ils peuvent même faire de petits calculs (câblés) (comme déterminer si un nombre binaire est divisible par trois ) mais cela ne compte pas.

Une petite histoire. Vous êtes sur une grande place rectangulaire dans une ville célèbre. Les habitants vous disent que la place est en fait carrée. Si vous pouvez compter, vérifiez si les nombres horizontal et vertical de tuiles correspondent en comptant les tuiles le long des côtés du carré. Si vous ne pouvez pas compter, vous pouvez toujours vérifier la réclamation: commencez dans un coin et marchez en diagonale. Si vous atteignez exactement le coin opposé, vous avez un carré.

Dans votre exemple, la fsa teste si une chaîne a un nombre égal de et en comptant ces nombres sur deux bandes de sortie différentes. Un autre appareil doit faire la comparaison finale, sauf si vous avez une astuce pour gérer les lettres $a$ $b$ $a$ et par paires et les séparer les unes des autres. Comme sur la place. $b$

Maintenant, un modèle plus formel avec lequel comparer. Selon le théorème de Chomsky – Schützenberger, chaque langage sans contexte est l'inverse d'une transduction à états finis du langage Dyck sur deux paires de crochets (il n'est pas dit comme ça sur wikipedia, mais vous devez me croire). Maintenant, le transducteur à états finis peut "accepter" son langage sans contexte $L$ $T$ $D_2$ $L = T^{-1}(D_2)$ $T$ $L$ comme suit (pour chaque langue son propre transducteur). Sur l'entrée transforme la chaîne en la série (supposée) de pops et de pushs du pda pour $T$ , puis testez si le résultat est un comportement de refoulement, c'est-à-dire que le résultat est une chaîne dans ) $L$ $D_2$ . (Détails techniques omis, mais c'est ce que prétend le théorème de Ch-Sch: on a ssi $w\in T^{-1}(D_2)$ $T(w) \in D_2$

Mon point ici est que certains "calculs" sont effectués par le transducteur mais beaucoup de puissance est cachée dans le test avec $D_2$ . De même, votre exemple, où deux lettres sont triées sur deux bandes.

Hendrik Jan
la source

Je peux construire un DFA qui compte entre

et

(fixes

) ou même dans

. C'est plus que n'importe quel ordinateur humain ou réel. Comment appelleriez-vous compter?

0

$0$

2^{n!}

$2^{n!}$

n

$n$

N

$\mathbb{N}$

Raphael

@Raphael. Sûr. Et des nombres facilement supérieurs à cela. Arrêtez d'enseigner que les langues sans contexte sont plus puissantes que les langues normales: elles sont les mêmes (au moins pour les chaînes de longueur au plus

). Je rigole. Se référer à de vrais langages informatiques comme celui-ci rend tout état fini n'est-ce pas? Les automates à états finis ne comptent pas! Ils distinguent simplement un nombre fini d'États, bien que ce nombre puisse être très grand.

2^{n!}

$2^{n!}$

Hendrik Jan

Mais la façon dont les ALE sont habituellement présentées, elles ne sont «autorisées» qu'à dire «oui» (acceptées) ou «non» (non acceptées). Compte tenu de cela, personne ne pouvait construire une FSA qui compte. Si nous lui permettons de signaler (par exemple imprimer) le (numéro de) l'état dans lequel il se trouve lorsqu'il se termine, alors il peut compter, mais uniquement jusqu'à une limite donnée par le nombre d'états. Mais si nous l'autorisons à imprimer, alors il est trivial de construire un FSA à état unique qui imprime (disons) 1 chaque fois qu'il lit un symbole dans la chaîne d'entrée, rapportant ainsi le compte dans la représentation de pointage. Quel est le problème avec cette idée?

Torbjörn

Et si nous oublions le rapport / l'impression et pensons plutôt en termes de représentations internes, un FSA peut compter les symboles dans une chaîne, mais pas dans un long arbitraire. Bien entendu, la FSA à un seul État ne peut pas compter du tout.

Torbjörn

k

$k$

1

@Shaull: Merci pour votre réponse! Je suis nouveau sur StackExchange et je ne sais pas commenter une réponse, je choisis donc d'écrire une réponse à la place, dans l'espoir d'être pardonné.

Hmm, il me semble qu'un berger comptant ses moutons en écrivant une marque sur une feuille de papier pour chaque mouton qu'il voit, ou un prisonnier comptant les jours où il est en prison en écrivant des marques sur le mur, comptent. Pourquoi n marques sur une feuille de papier ou sur un mur ne seraient-elles pas considérées comme une représentation du nombre n? N'est-ce pas ce qu'on appelle une représentation de pointage? AFAICS, elle n'est en aucun cas inférieure à (disons) une représentation binaire, sauf qu'elle utilise plus d'espace.

Je suppose que pour vous alors, "savoir" signifie qu'il a une représentation interne du compte à la fin. Alors, bien sûr, il est évident qu'une FSA de FST ne peut pas calculer la longueur d'une chaîne arbitraire. Mais si nous n'avons pas besoin de connaissances dans ce sens, mais demandons seulement que le FSA ou le FST soient capables de dire le résultat à un observateur externe, alors il me semble que présenter le décompte dans un format de pointage devrait être correct.

De plus, si un FSA est équipé à la fois d'une entrée et d'une sortie incrémentielles, il devrait en principe pouvoir utiliser son environnement externe comme une mémoire de lecture / écriture, et donc être aussi puissant qu'une machine de Turing. Droite?

Merci d'avoir soulevé le cas de la comparaison. Maintenant, il semble que si nous levons l'exigence d'une représentation interne, et nous demandons seulement que la machine soit capable de présenter le résultat à un observateur externe, alors nous pourrions facilement construire un FSM qui pourrait produire une sorte de présentation graphique du résultat. Supposons que le FSM, lors des lectures "aaaaaabbbbbb" a écrit

000000
000000

puis, comme les barres sont de même longueur, le FSM a accepté la chaîne "aaaaaabbbbbb". Deux barres de même longueur signifient "oui", des longueurs différentes signifient "non".

Je suppose que je plie les règles, mais c'est ce que je veux puisque je m'intéresse aux hypothèses plus ou moins implicites qui sont faites dans le domaine de la linguistique mathématique.

Torbjörn
la source

F S A_{W O C}

$FSA_{WOC}$

{a^{n} | n is prime}

$\{a^n | n \mbox{ is prime }\}$

Je pense que la différence entre les exemples que vous donnez et la sortie FST est que le berger peut lire les lignes après leur écriture, contrairement à un FSM. Il en va de même pour la comparaison.

Shaull

Vous pouvez commenter en cliquant sur le lien "ajouter un commentaire" sous n'importe quel post.

Raphael

Toute FSA construite pour compter un troupeau peut compter ce troupeau. Aucune FSA construite ne peut compter aucun troupeau. La question fondamentale est de savoir si le berger sait seulement compter assez loin pour au moins compter son propre troupeau, ou s'il peut utiliser la gamme complète des nombres naturels. D'après mon expérience, nous, les humains, devons explicitement faire la transition entre les deux capacités à un moment donné de notre éducation mathématique.

reinierpost

1

Les FSM peuvent "compter" dans une plage finie / nombre d'étapes signifié par des transitions d'état. cependant, ils ne peuvent pas compter au-delà d'un nombre fini d'étapes.

il y a un sens dans lequel une machine de type FSA peut compter. une machine étroitement apparentée est appelée un transducteur à états finis . le transducteur peut en effet compter au sens d'entrée et de sortie "canalisées". un seul transducteur peut prendre une séquence d'entrée (disons en binaire) et la "transduire" en une séquence de sortie qui est incrémentée. puis on "enchaîne" les transducteurs (identiques) comptés par 1, chacun incrémentant son entrée de 1 et la sortant. c'est aussi comme un "algorithme de streaming" rudimentaire .

vzn
la source

plus de détails: le transducteur peut incrémenter le travail dans l'ordre "lsb" à "msb", c'est-à-dire "le plus petit bit sig" à "le plus bit sig" en utilisant une logique similaire à l' additionneur complet EE .

vzn

Les transducteurs à états finis fyi ne semblent pas avoir été beaucoup étudiés. il existe une autre application intéressante à la conjecture collatz dans la création d'une machine qui calcule les itérations. toute personne intéressée par la théorie / discussion plz me contacter dans le chat ou sur mon blog .

vzn

Une FSA peut-elle compter?

Réponses: