Echivalența stărilor DFA accesibile
Grupează stările accesibile ale unui DFA complet cu cel mult 16 stări și patru simboluri după sufixele acceptate.
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| Proiect | Testează echivalența și distingerea, excluzând stările inaccesibile și respingând tranzițiile invalide. |
|---|---|
| Verifică înainte de aplicare | Compară comportamentul real cu rezultatul așteptat. Dacă o verificare eșuează, cercetează cauza înainte de alte modificări. |
| Modele | Configurează un endpoint compatibil OpenAI sau Anthropic cu URL-ul de bază și cheia API, dacă este necesară. Testează conexiunea. Serverul local trebuie să ruleze; instrumentele externe pot transmite date separat. |
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 = refinedSimplifică codul cu stare păstrând comportamentul observabil
StateAmaranth este un spațiu de lucru Windows pentru examinarea software-ului cu stare împreună cu un model IA conectat. Începe cu evenimentele acceptate de sistem și rezultatele pe care le poate observa apelantul. O cerere de simplificare a stărilor necesită acest context, astfel încât o reprezentare mai mică să nu devină obiectivul în detrimentul comportamentului aplicației.
Exemplul determinist furnizat oferă o sarcină concretă: examinarea echivalenței între stările accesibile, păstrând comportamentul de acceptare. Adu în discuție tabelul de tranziții și starea inițială dorită. Cere modelului să explice distincțiile importante înainte să soliciți modificări, mai ales dacă aplicația înconjurătoare expune mai mult decât un simplu rezultat de acceptare sau respingere.
Examinează orice grupare propusă pe secvențe scurte de evenimente cu rezultate cunoscute. Include trasee care ajung în stări diferite și cazuri cu intrări inaccesibile, apoi rulează verificările în proiect. Examinează și interfața care folosește gruparea, deoarece schimbarea numerotării sau reprezentării stărilor poate strica apelanții chiar dacă se păstrează comportamentul de acceptare.
Un model de IA fără restricții poate fi selectat printr-un endpoint acceptat compatibil cu OpenAI sau Anthropic care îl oferă. Configurează credențiale după necesități și verifică limitele contextului și disponibilitatea instrumentelor. Comportamentul răspunsurilor modelului rămâne dependent de endpoint; dovezile unei simplificări sigure provin din observațiile declarate și verificările efectuate de tine.
Întrebări pentru refactorizarea unui automat
- Ce trebuie considerat comportament observabil în cerere?
Enumeră ieșirile sau deciziile pe care se bazează apelanții, nu doar numele interne ale stărilor. Dacă tranzițiile emit acțiuni sau erori, include-le. Exemplul ilustrat bazat pe acceptare poate fi mai restrâns decât comportamentul pe care aplicația reală trebuie să îl păstreze.
- Pot fi întotdeauna unite în aplicație stările echivalente ca acceptare?
Nu fără verificarea restului contractului. Aplicația poate expune identificatori, acțiuni sau alte efecte dependente de stare. Cere asistentului să examineze codul care le folosește înainte să aplice un argument de echivalență bazat doar pe acceptare.
- Cum trebuie tratate stările inaccesibile în timpul examinării?
Precizează starea inițială și modul de determinare a accesibilității. Include un caz de test cu intrări inaccesibile și ieșirea dorită. Examinează dacă apelanții așteaptă ca acele intrări să rămână identificabile înainte să accepți eliminarea sau regruparea propusă.
- Ce testez după modificarea identificatorilor stărilor?
Verifică tranzițiile, referințele stocate și orice interfață care afișează sau folosește identificatorii. Rulează secvențe comportamentale, precum și verificări ale structurii grupării returnate. Păstrarea acceptării singure nu dovedește că respectivul cod dependent interpretează încă reprezentarea corect.
StateAmaranth · Actualizat 2026-10-25