Еквівалентність досяжних станів DFA
Згрупуйте досяжні стани повного DFA з максимум 16 станами й чотирма символами за прийнятими суфіксами.
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| Проєкт | Перевірте еквівалентні та розрізнювані стани, виключаючи недосяжні й відхиляючи хибні переходи. |
|---|---|
| Перевірте перед застосуванням | Порівняйте фактичну поведінку з очікуваним результатом. Якщо перевірка не проходить, з’ясуйте причину перед наступними змінами. |
| Моделі | Налаштуйте OpenAI-сумісний або Anthropic endpoint із базовою URL-адресою та API-ключем, якщо він потрібен. Перевірте з’єднання. Локальний сервер моделі має працювати; віддалені інструменти можуть окремо передавати дані. |
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Спрощуйте код зі станом, зберігаючи спостережувану поведінку
StateAmaranth — робоче середовище програмування у Windows для перевірки програм зі станом разом із підключеною моделлю ШІ. Почніть із подій, які система приймає, та результатів, які може спостерігати код виклику. Запиту на спрощення станів потрібен цей контекст, щоб менше подання не стало метою на шкоду поведінці програми.
Наданий приклад детермінованих станів дає конкретне завдання: дослідити еквівалентність досяжних станів зі збереженням поведінки прийняття. Додайте до обговорення таблицю переходів і задуманий початковий стан. Попросіть модель пояснити важливі відмінності перед запитом змін, особливо якщо навколишня програма надає більше, ніж простий результат прийняття або відхилення.
Перевірте запропоноване групування на коротких послідовностях подій із відомими результатами. Додайте шляхи до різних станів і випадки з недосяжними записами, а потім запустіть перевірки у проєкті. Також дослідіть інтерфейс, який використовує групування, адже зміна нумерації чи подання станів може зламати виклики навіть зі збереженням поведінки прийняття.
Модель ШІ без обмежень можна вибрати через підтримувану кінцеву точку, сумісну з OpenAI, або Anthropic, яка її пропонує. Налаштуйте облікові дані за потреби й перевірте межі контексту та доступність інструментів. Поведінка відповідей моделі залежить від кінцевої точки; докази безпечного спрощення походять із заявлених вами спостережень і виконаних перевірок.
Запитання щодо рефакторингу автомата
- Що вважати спостережуваною поведінкою в запиті?
Перелічіть виходи або рішення, на які покладається код виклику, а не лише внутрішні назви станів. Якщо переходи породжують дії чи помилки, додайте їх. Показаний приклад на основі прийняття може бути вужчим за поведінку, яку має зберігати фактична програма.
- Чи завжди можна об’єднати стани з еквівалентним прийняттям у моїй програмі?
Не без перевірки решти контракту. Програма може надавати ідентифікатори, дії або інші залежні від стану ефекти. Попросіть помічника дослідити цих споживачів перед застосуванням аргументу еквівалентності лише на основі прийняття.
- Як обробляти недосяжні стани під час перевірки?
Зазначте початковий стан і спосіб визначення досяжності. Додайте тест із недосяжними записами та потрібним результатом. Перевірте, чи очікує код виклику збереження ідентифікованості цих записів, перш ніж приймати видалення або перегрупування.
- Що тестувати після зміни ідентифікаторів станів?
Перевірте переходи, збережені посилання та всі інтерфейси, що показують або використовують ідентифікатори. Запустіть поведінкові послідовності разом із перевірками форми поверненого групування. Саме збереження прийняття не доводить, що залежний код усе ще правильно тлумачить подання.
StateAmaranth · Оновлено 2026-10-25