Quelle est la connexion entre les circuits combinatoires et les automates d'état finis?
-
05-11-2019 - |
Question
Le diagramme sur la page wikipedia de FSA montre la hiérarchie des dispositifs de calcul, dans ce diagramme, il est indiqué que les machines d'état finies sont supérieures aux circuits combinatoires.
Les circuits combinatoires sont le modèle de logique propositionnelle, c'est-à-dire que les deux sont équivalents, où nous faisons une discussion sur les valeurs de vérité des variables et les connecteurs logiques. Tandis que les modèles au-delà de la FSA traitent les chaînes et décident de l'adhésion d'une chaîne avec une langue.
S'il existe un lien entre ces deux modèles, il doit y avoir une certaine relation entre la logique propositionnelle et les langues régulières / sans contexte / récursives.
Comment pouvons-nous construire une FSA correspondante pour un circuit combinatoire donné?
Pas de solution correcte