Na}{

File Content: `FSA.py`

class FiniteAutomaton:
    def __init__(self, start_state, dump_state=''):
        self.start_state = start_state
        self.dump_state = dump_state
        self.table = {self.dump_state: {}}
        self.unresolved_composites = []
        self.resolved_composites = []
        self.composite_memo = {}
        self.is_updated = 1

    def __setitem__(self, xxx_todo_changeme, x):
        (state, symbol) = xxx_todo_changeme
        self.table.setdefault(state, {})[symbol] = x
        self.is_updated = 1

    def add_transition(self, state, symbol, *nexts):
        if len(nexts) == 1:
            c = nexts[0]
        else:
            for n in nexts:
                if n not in self.table:
                    self.table[n] = {}

            c = self.new_composite(nexts)
        self[state, symbol] = c
        if c not in self.table:
            self.table[c] = {}

    def get_row_items(self, state):
        try:
            x = list(self.table[state].items())
        except KeyError:
            return ()
        ris = []
        for k, v in x:
            if isinstance(v, CompositeState):
                for vi in v:
                    ris.append((k, vi))
            else:
                ris.append((k, v))
        return ris

    def make_deterministic(self):
        # Resolve all unresolved composite states so we become deterministic

        while self.unresolved_composites:
            composites = self.unresolved_composites
            self.unresolved_composites = []
            for c in composites:
                ds = {}
                l = []
                for a in c:
                    for k, v in self.get_row_items(a):
                        ds.setdefault(k, []).append(v)
                for k, v in list(ds.items()):
                    for a in c:
                        if k not in self.table[a]:
                            v.append(self.dump_state)
                            break
                for k, v in list(ds.items()):
                    self.add_transition(c, k, *v)

    def get_all_input_symbols(self):
        syms = {}
        for state, trans in list(self.table.items()):
            for k, v in trans:
                syms[k] = 1
        return syms

    def get_all_states(self):
        return self.table

    def get_all_final_states(self):
        return {}

    def get_composites(self):
        if self.is_updated:
            self.make_deterministic()
        return list(self.composite_memo.values())

    def get_transition_classes(self):
        # Get classes of states that have the same outgoing transitions
        tc = {}
        tck = {}
        for k, v in list(self.table.items()):
            trans = list(v.keys())
            trans.sort()
            trans = tuple(trans)
            ks = tc.get(trans)
            if ks is None:
                ks = []
                tc[trans] = ks
            ks.append(k)
            tck[k] = ks
        return tc, tck

    def get_minimized_dfa(self, finals):
        def markall(finals, tcv, table):
            def psrmark(l):
                for pq in l:
                    if pq in PS:
                        l1 = PS[pq]
                        del PS[pq]
                        if l1:
                            psrmark(l1)
            PS = {}
            for Q in tcv:
                for ip, p in enumerate(Q):
                    for q in Q[ip+1:]:
                        if (p in finals) == (q in finals):
                            PS[(p, q)] = ()

            for pq in list(PS.keys()):
                p, q = pq
                dp = table[p]
                dq = table[q]
                # Now we know they contain the same symbols
                dps = []
                for a in dp:
                    dpa = dp[a]
                    dqa = dq[a]
                    if dpa is not dqa:
                        dpadqa = (dpa, dqa)
                        if dpadqa in PS:
                            dps.append(dpadqa)
                        else:
                            dqadpa = (dqa, dpa)
                            if dqadpa in PS:
                                dps.append(dqadpa)
                            else:
                                l = PS[pq]
                                del PS[pq]
                                if l is not ():
                                    psrmark(l)
                                break
                else:
                    for dpadqa in dps:
                        l = PS[dpadqa]
                        if l is ():
                            l = [pq]
                            PS[dpadqa] = l
                        else:
                            l.append(pq)
            return PS

        def combine(QS, PQS):
            eqs = {}
            for Q in QS:
                for p in Q:
                    eqs[p] = [p]

            for p, q in PQS:
                #
                # Combine to equivalence classes
                #
                # Now we know that p, q are combinable
                #
                ep = eqs[p]
                eq = eqs[q]
                if eq is not ep:
                    if len(eq) > len(ep):
                        eq, ep = ep, eq
                    ep.extend(eq)
                    for q in eq:
                        eqs[q] = ep

            return eqs

        def finalize(eqs):
            csbyid = {}         # Composite state by identity of atomic state list
            csbyas = {}         # Composite state by atomic state

            i = 0
            for eq in list(eqs.values()):
                ideq = id(eq)
                if ideq not in csbyid:
                    c = 'MS%d' % i
                    i += 1
                    csbyid[ideq] = eq[0], c
                    for s in eq:
                        csbyas[s] = c

            fsa = self.__class__(csbyas[self.start_state])
            fsa.final_states = {}

            for cs0, cst in list(csbyid.values()):
                fsa.table[cst] = trans = {}
                for a, s in list(self.table[cs0].items()):
                    trans[a] = csbyas[s]
                if cs0 in finals:
                    fsa.final_states[cst] = 1

            return fsa

        if self.is_updated:
            self.make_deterministic()
            tctck = self._tctck = self.get_transition_classes()
            self.is_updated = 0
        else:
            tctck = self._tctck

        tc, tck = tctck
        tcv = list(tc.values())
        PS = markall(finals, tcv, self.table)
        eqs = combine(tcv, PS)
        fsa = finalize(eqs)
        return fsa

    def new_composite(self, args):
        cs = CompositeState(list(dict([(arg, 1) for arg in args]).keys()))
        if len(cs) == 1:
            return args[0]
        try:
            return self.composite_memo[cs]
        except KeyError:
            self.composite_memo[cs] = cs
            self.unresolved_composites.append(cs)
            return cs

    def pp(self):
        ks = list(self.table.keys())
        ks.sort()
        num = dict([(s, i) for i, s in enumerate(ks)])
        for s in ks:
            k = self.table[s]
            print('%d: %s' % (num[s], s))
            cs = list(k.keys())
            cs.sort()
            for c in cs:
                v = k[c]
                print('   %r  -> #%d: %s' % (c, num[v], v))


class CompositeState(tuple):
    pass
Name	Size	Permission
__pycache__	---	0755
Cat.py	4088 bytes	0644
Code.py	1056 bytes	0644
Descriptor.py	801 bytes	0644
FSA.py	7376 bytes	0644
Glue.py	13658 bytes	0644
Help.py	6873 bytes	0644
IterPermute.py	2273 bytes	0644
KanExtension.py	21205 bytes	0644
KnuthBendix.py	9023 bytes	0644
RE.py	24154 bytes	0644
RE_Rect.py	10635 bytes	0644
__init__.py	87 bytes	0644
cmd.py	15070 bytes	0644
etc.py	1697 bytes	0644
textView.py	3146 bytes	0644
tkcursors.py	2177 bytes	0644
xterm.py	2365 bytes	0644
File Content: FSA.py

File Content: `FSA.py`
