Ekvivalence dosažitelných stavů DFA
Seskupte dosažitelné stavy úplného DFA s nejvýše 16 stavy a čtyřmi symboly podle přijímaných přípon.
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| Projekt | Ověřte ekvivalentní a rozlišitelné stavy, vynechte nedosažitelné a odmítněte neplatné přechody. |
|---|---|
| Před použitím zkontrolujte | Porovnejte skutečné chování s očekávaným výsledkem. Pokud kontrola selže, před dalšími změnami zjistěte příčinu. |
| Modely | Nastavte endpoint kompatibilní s OpenAI nebo Anthropic pomocí základní URL a případného API klíče. Otestujte připojení. Lokální server modelu musí běžet; vzdálené nástroje mohou data odesílat samostatně. |
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 = refinedZjednodušujte stavový kód při zachování pozorovatelného chování
StateAmaranth je pracovní prostředí pro programování ve Windows pro kontrolu stavového softwaru s připojeným modelem AI. Začněte událostmi, které systém přijímá, a výsledky pozorovatelnými volajícím. Požadavek na zjednodušení stavů tento kontext potřebuje, aby se menší reprezentace nestala cílem na úkor chování aplikace.
Dodaný příklad deterministických stavů nabízí jednu konkrétní úlohu: zkoumání ekvivalence mezi dosažitelnými stavy při zachování přijímacího chování. Do diskuse přineste tabulku přechodů a zamýšlený počáteční stav. Před žádostí o změny požádejte model o vysvětlení důležitých rozdílů, zejména pokud okolní aplikace zpřístupňuje více než jednoduchý výsledek přijmout či odmítnout.
Každé navržené seskupení prověřte na krátkých posloupnostech událostí se známými výsledky. Zahrňte cesty vedoucí do různých stavů a případy s nedosažitelnými položkami a poté spusťte kontroly v projektu. Prověřte i rozhraní používající seskupení, protože změna číslování nebo reprezentace stavů může narušit volající, i když se přijímací chování zachová.
Model AI bez omezení lze zvolit přes podporovaný koncový bod kompatibilní s OpenAI nebo Anthropic, který jej nabízí. Podle potřeby nastavte přihlašovací údaje a ověřte limity kontextu a dostupnost nástrojů. Chování odpovědí modelu nadále závisí na koncovém bodu; důkazy bezpečného zjednodušení vycházejí z vašich stanovených pozorování a provedených kontrol.
Otázky k refaktoringu stavového automatu
- Co mám v požadavku považovat za pozorovatelné chování?
Vyjmenujte výstupy či rozhodnutí, na která volající spoléhají, nejen interní názvy stavů. Pokud přechody vyvolávají akce nebo chyby, zahrňte je. Ukázkový příklad založený na přijímání může být užší než chování, které skutečná aplikace musí zachovat.
- Lze v aplikaci vždy sloučit stavy se stejným přijímacím chováním?
Ne bez kontroly zbytku kontraktu. Aplikace může zpřístupňovat identifikátory, akce či jiné účinky závislé na stavu. Před použitím argumentu ekvivalence založeného jen na přijímání požádejte asistenta o kontrolu těchto navazujících míst.
- Jak při kontrole zacházet s nedosažitelnými stavy?
Určete počáteční stav a způsob určení dosažitelnosti. Přidejte testovací případ s nedosažitelnými položkami a zamýšleným výstupem. Před přijetím navrženého odstranění či přeskupení prověřte, zda volající očekávají zachování identifikovatelnosti těchto položek.
- Co otestovat po změně identifikátorů stavů?
Zkontrolujte přechody, uložené reference a každé rozhraní zobrazující či používající identifikátory. Vedle kontrol tvaru vráceného seskupení spusťte i behaviorální posloupnosti. Samotné zachované přijímání nedokazuje, že závislý kód reprezentaci stále správně interpretuje.
StateAmaranth · Aktualizováno 2026-10-25