Équivalence des états DFA accessibles
Regroupez les états accessibles d’un DFA complet d’au plus 16 états et quatre symboles selon les suffixes acceptés.
def dfa_classes(table, accepting):
if type(table) is not list or not 1 <= len(table) <= 16:
raise ValueError("state count")
n = len(table)
if type(table[0]) is not list or not 1 <= len(table[0]) <= 4:
raise ValueError("alphabet size")
width = len(table[0])
if any(type(row) is not list or len(row) != width or
any(type(x) is not int or not 0 <= x < n for x in row)
for row in table):
raise ValueError("complete transition table")
if type(accepting) is not set or any(
type(x) is not int or not 0 <= x < n for x in accepting):
raise ValueError("accepting states")
seen, pending = {0}, [0]
while pending:
for dest in table[pending.pop()]:
if dest not in seen:
seen.add(dest); pending.append(dest)
groups = [g for g in (seen & accepting, seen - accepting) if g]
while True:
owner = {s: i for i, g in enumerate(groups) for s in g}
refined = []
for group in groups:
buckets = {}
for state in sorted(group):
key = tuple(owner[d] for d in table[state])
buckets.setdefault(key, set()).add(state)
refined.extend(buckets.values())
if len(refined) == len(groups):
return sorted([sorted(g) for g in refined])
groups = refined| Projet | Testez équivalence et distinction, en excluant les états inaccessibles et en rejetant les transitions invalides. |
|---|---|
| Vérifiez avant d’appliquer | Comparez le comportement observé au résultat attendu. Si une vérification échoue, cherchez la cause avant de poursuivre les modifications. |
| Modèles | Configurez un endpoint compatible OpenAI ou Anthropic avec son URL de base et une clé API si nécessaire. Testez la connexion. Un serveur local doit fonctionner ; les outils distants peuvent transmettre des données séparément. |
def dfa_classes(table, accepting):
if type(table) is not list or not 1 <= len(table) <= 16:
raise ValueError("state count")
n = len(table)
if type(table[0]) is not list or not 1 <= len(table[0]) <= 4:
raise ValueError("alphabet size")
width = len(table[0])
if any(type(row) is not list or len(row) != width or
any(type(x) is not int or not 0 <= x < n for x in row)
for row in table):
raise ValueError("complete transition table")
if type(accepting) is not set or any(
type(x) is not int or not 0 <= x < n for x in accepting):
raise ValueError("accepting states")
seen, pending = {0}, [0]
while pending:
for dest in table[pending.pop()]:
if dest not in seen:
seen.add(dest); pending.append(dest)
groups = [g for g in (seen & accepting, seen - accepting) if g]
while True:
owner = {s: i for i, g in enumerate(groups) for s in g}
refined = []
for group in groups:
buckets = {}
for state in sorted(group):
key = tuple(owner[d] for d in table[state])
buckets.setdefault(key, set()).add(state)
refined.extend(buckets.values())
if len(refined) == len(groups):
return sorted([sorted(g) for g in refined])
groups = refinedSimplifiez le code à états en préservant le comportement observable
StateAmaranth est un espace de programmation pour Windows permettant d’examiner des logiciels à états avec un modèle d’IA connecté. Commencez par les événements acceptés par le système et les résultats observables par un appelant. Une demande de simplification des états nécessite ce contexte pour qu’une représentation plus petite ne devienne pas l’objectif au détriment du comportement de l’application.
L’exemple fourni d’états déterministes donne une tâche concrète : examiner l’équivalence entre états accessibles en préservant le comportement d’acceptation. Ajoutez votre table de transitions et l’état initial voulu à la discussion. Demandez au modèle d’expliquer quelles distinctions comptent avant de demander des modifications, surtout si l’application environnante expose davantage qu’un simple résultat d’acceptation ou de rejet.
Examinez tout regroupement proposé à l’aide de courtes séquences d’événements aux résultats connus. Incluez des chemins atteignant différents états et des cas avec des entrées inaccessibles, puis exécutez les vérifications dans votre projet. Examinez aussi l’interface consommant le regroupement : un changement de numérotation ou de représentation des états peut casser les appelants même si le comportement d’acceptation est préservé.
Un modèle d’IA sans restrictions peut être sélectionné via un point de terminaison compatible OpenAI ou Anthropic pris en charge qui en propose un. Configurez les identifiants si nécessaire et vérifiez les limites de contexte et la disponibilité des outils. Le comportement de réponse du modèle reste dépendant du point de terminaison ; les preuves permettant une simplification sûre proviennent des observations définies et des vérifications effectuées.
Questions sur une refactorisation de machine à états
- Que considérer comme comportement observable dans ma demande ?
Listez les sorties ou décisions dont dépendent les appelants, pas seulement les noms des états internes. Si les transitions produisent des actions ou des erreurs, incluez-les. L’exemple illustré fondé sur l’acceptation peut être plus limité que le comportement à préserver dans votre application réelle.
- Des états équivalents pour l’acceptation peuvent-ils toujours être fusionnés ?
Pas sans vérifier le reste du contrat. L’application peut exposer des identifiants, des actions ou d’autres effets dépendant des états. Demandez à l’assistant d’examiner ces consommateurs avant d’appliquer un raisonnement d’équivalence fondé uniquement sur l’acceptation.
- Comment traiter les états inaccessibles pendant l’examen ?
Précisez l’état initial et la méthode déterminant l’accessibilité. Incluez un cas avec des entrées inaccessibles et la sortie voulue. Vérifiez si les appelants attendent que ces entrées restent identifiables avant d’accepter leur suppression ou regroupement proposé.
- Que tester après un changement d’identifiants d’états ?
Vérifiez les transitions, les références stockées et toute interface affichant ou consommant les identifiants. Exécutez des séquences comportementales et des contrôles de forme du regroupement renvoyé. Préserver l’acceptation seule ne prouve pas que le code dépendant interprète toujours correctement la représentation.
StateAmaranth · Mis à jour 2026-10-25