"""Owned epsilon-NFA subset construction with independent language check on 63 short strings."""
from collections import deque
import itertools,json
ALPHABET='ab';EPS={0:{1,3}};MOVES={(1,'a'):{1},(1,'b'):{2},(3,'b'):{3},(3,'a'):{4}};FINAL={2,4}
def closure(states,epsilon=None):
    epsilon=EPS if epsilon is None else epsilon
    seen=set(states);q=list(seen)
    while q:
        u=q.pop()
        for v in epsilon.get(u,set()):
            if v not in seen:seen.add(v);q.append(v)
    return frozenset(seen)
def transition(states,c):
    if c not in ALPHABET:raise ValueError('declared alphabet a,b only')
    return closure(set().union(*(MOVES.get((u,c),set())for u in states)))
def nfa_accept(word):
    states=closure({0})
    for c in word:states=transition(states,c)
    return bool(states&FINAL)
def construct():
    start=closure({0});ids={start:0};q=deque([start]);table={}
    while q:
        S=q.popleft();row={}
        for c in ALPHABET:
            T=transition(S,c)
            if T not in ids:ids[T]=len(ids);q.append(T)
            row[c]=ids[T]
        table[ids[S]]=row
    accept={i for S,i in ids.items()if S&FINAL};return ids,table,accept
def dfa_accept(word,table,accept):
    state=0
    for c in word:
        if c not in ALPHABET:raise ValueError('declared alphabet a,b only')
        state=table[state][c]
    return state in accept
def language(word):
    return bool(word)and ((word[-1]=='b'and all(c=='a'for c in word[:-1]))or(word[-1]=='a'and all(c=='b'for c in word[:-1])))
def demo():
    ids,table,accept=construct();rows=[]
    for n in range(6):
        for w in map(''.join,itertools.product(ALPHABET,repeat=n)):
            a=nfa_accept(w);b=dfa_accept(w,table,accept);c=language(w);assert a==b==c;rows.append({'word':w,'nfa':a,'dfa':b,'independent_language_definition':c})
    assert len(ids)==8 and len(rows)==63 and not nfa_accept('')and nfa_accept('aab')and nfa_accept('bba')and not nfa_accept('aba')
    dead=ids[frozenset()];assert table[dead]=={'a':dead,'b':dead}and dead not in accept
    assert closure({1})==frozenset({1})and closure({0})==frozenset({0,1,3})
    try:dfa_accept('آ',table,accept)
    except ValueError:invalid=True
    else:raise AssertionError('unknown symbol accepted')
    cycle={0:{1},1:{0,2},2:{1}};cycle_result=closure({0},cycle)
    assert cycle_result==frozenset({0,1,2}) and closure(set(),cycle)==frozenset()
    return {'authored_nfa':{'states':[0,1,2,3,4],'start':0,'epsilon':{str(u):sorted(v)for u,v in EPS.items()},'symbol_moves':[{'from':u,'symbol':c,'to':sorted(v)}for(u,c),v in MOVES.items()],'accepting':sorted(FINAL)},'language':'a*b OR b*a; each branch ends in exactly one opposite symbol','reachable_dfa_states':[{'id':i,'nfa_subset':sorted(S),'accepting':i in accept,'transitions':table[i]}for S,i in ids.items()],'dead_state':dead,'independent_short_string_checks':rows,'bounded_checks_not_general_proof':True,'separate_epsilon_cycle_fixture':{'epsilon':{str(u):sorted(v)for u,v in cycle.items()},'start':[0],'closure':sorted(cycle_result),'same_closure_function_used':True,'empty_start_stays_empty':True,'does_not_change_main_nfa_or_dfa':True},'invalid_alphabet_rejected':invalid,'minimal_dfa_or_full_regex_engine_claimed':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=False,indent=2))