sofic is a Python package for hidden Markov models, symbolic dynamics,
finite state machines, and other stochastic symbol generators.
Clone the repository and install development dependencies with uv:
git clone https://github.com/dit/sofic.git
cd sofic
uv sync --extra devRun tests with uv run pytest. See the generalinfo page in the Sphinx
docs for linting, type checking, and documentation builds.
Many natural and engineered processes produce sequences of symbols whose
statistics are governed by latent structure: hidden states, transition rules,
or algebraic constraints on allowed paths. sofic collects algorithms and
data structures for representing, simulating, and analyzing such generators
behind a single, composable Python API.
Every model is a graph-backed state machine, so the same objects support construction, validation, simulation, visualization, (de)serialization, and a large library of structural and information-theoretic measures. The three main families are:
- Stochastic generators (
sofic.generators) — Markov chains, hidden Markov models (Moore and Mealy presentations), ε-machines, probabilistic finite automata, mixed-state presentations, and quasiprobabilistic generators. These assign probabilities to sequences. - Finite automata (
sofic.automata) — DFAs, NFAs, transducers (Mealy/Moore machines), regular languages, Büchi automata, visibly pushdown and nested-word automata, and residual finite-state automata. These recognize or transform languages. - Symbolic shifts (
sofic.shifts) — shifts of finite type, sofic shifts, topological Markov chains, and Dyck/sofic-Dyck shifts. These describe the support (set of allowed sequences) of a process.
The package builds on NumPy, SciPy, and NetworkX and is designed to sit alongside the dit ecosystem for information-theoretic analysis of the processes these models describe.
pip install soficOptional extras:
sofic[viz]— Graphviz diagrams in terminals and Jupytersofic[bayes]— PyMC/ArviZ backends for Bayesian inferencesofic[test]— pytest, hypothesis, and graphviz for the test suitesofic[docs]— Sphinx, IPython, and matplotlib for the docssofic[dev]— linting, type checking, docs, and all of the above
The basic workflow is the same for every model: build (or load) a generator,
call validate(), then compute properties or convert to another
presentation. States can be any hashable object and every model exposes
states(), transitions(), draw(), and to_yaml().
Markov chain — a visible-state process. Edges carry P(target | source):
fromsoficimportMarkovChainmc=MarkovChain(initial_distribution={"sunny": 0.5, "rainy": 0.5})
mc.add_transition("sunny", "sunny", 0.9)
mc.add_transition("sunny", "rainy", 0.1)
mc.add_transition("rainy", "sunny", 0.5)
mc.add_transition("rainy", "rainy", 0.5)
mc.validate()
mc.stationary_distribution() # array([0.8333, 0.1667])mc.entropy_rate() # 0.5575 bits/symbolmc.is_deterministic() # FalseMoore HMM — hidden states with an emission law P(observation | state) on
states and P(target | source) on edges:
fromsoficimportMooreHMMmoore=MooreHMM(
observation_alphabet=frozenset({"H", "T"}),
initial_distribution={0: 0.5, 1: 0.5},
)
moore.add_transition(0, 0, 0.5)
moore.add_transition(0, 1, 0.5)
moore.add_transition(1, 0, 0.5)
moore.add_transition(1, 1, 0.5)
moore.set_emission_distribution(0, {"H": 0.9, "T": 0.1})
moore.set_emission_distribution(1, {"H": 0.1, "T": 0.9})
moore.validate()
moore.stationary_distribution() # array([0.5, 0.5])moore.log_likelihood(["H", "H", "T", "T"]) # -2.7726 (log2)observations, hidden=moore.sample(6) # simulate the processMealy HMM — hidden states with a joint transition/emission law
P(target, symbol | source) on edges. Here is the golden-mean process
(consecutive 1s are forbidden):
fromsoficimportMealyHMMgm=MealyHMM(
observation_alphabet=frozenset({0, 1}),
initial_distribution={"A": 2/3, "B": 1/3},
)
gm.add_transition("A", "A", 0, 0.5) # source, target, symbol, probabilitygm.add_transition("A", "B", 1, 0.5)
gm.add_transition("B", "A", 0, 1.0)
gm.validate()
gm.entropy_rate() # 0.6667 bits/symbolgm.is_unifilar() # Truegm.word_probability([1, 0, 1]) # 0.1667Many canonical models ship in sofic.examples, so the golden mean is
also just from sofic.examples import golden_mean; gm = golden_mean(0.5).
ε-machine — the minimal unifilar (causal-state) presentation of a stationary process. Build one from any HMM, from an observed sequence, or directly, and read off computational-mechanics quantities:
fromsoficimportEpsilonMachineeps=EpsilonMachine.from_hmm(gm) # minimize an HMM presentation# eps = EpsilonMachine.from_sequence(data, method="cssr", Lmax=4) # infereps.statistical_complexity() # 0.9183 bits (C_mu)eps.entropy_rate() # 0.6667 bits/symbol (h_mu)eps.markov_order() # 1eps.cryptic_order() # 1DFA — a deterministic recognizer. This one accepts strings with an even
number of bs (states are added before their transitions so determinism can
be checked as you go):
fromsoficimportDFAdfa=DFA(
input_alphabet=frozenset({"a", "b"}),
initial_states=frozenset({"even"}),
accepting_states=frozenset({"even"}),
)
dfa.graph.add_state("even")
dfa.graph.add_state("odd")
dfa.add_transition("even", "even", "a")
dfa.add_transition("even", "odd", "b")
dfa.add_transition("odd", "odd", "a")
dfa.add_transition("odd", "even", "b")
dfa.validate()
dfa.recognizes("abba") # True (two b's)dfa.recognizes("abbb") # False (three b's)dfa.minimize() # DFA(2 states, 4 transitions)dfa.to_regex() # 'a*|a*b(?:...)*ba*'NFA — nondeterministic, with first-class ε-transitions. Determinize to a DFA when you need one:
fromsoficimportNFAnfa=NFA(
input_alphabet=frozenset({"a", "b"}),
initial_states=frozenset({"q0"}),
accepting_states=frozenset({"q2"}),
)
nfa.add_transition("q0", "q0", "a")
nfa.add_transition("q0", "q0", "b")
nfa.add_transition("q0", "q1", "a")
nfa.add_transition("q1", "q2", "b")
nfa.validate()
nfa.recognizes("ab") # Truedfa=nfa.determinize()Transducer (Mealy machine) — maps input words to output words. This one inverts bits:
fromsoficimportMealyMachineinv=MealyMachine(
input_alphabet=frozenset({"0", "1"}),
output_alphabet=frozenset({"0", "1"}),
initial_states=frozenset({"q"}),
)
inv.add_transition("q", "q", "0", "1") # source, target, input, outputinv.add_transition("q", "q", "1", "0")
inv.validate()
inv.transduce("0110") # {('1', '0', '0', '1')}All automata also support union, intersection, complement,
difference, concat, and kleene_star (see the
LabeledAutomaton base class).
Shift of finite type — the set of sequences avoiding a finite list of
forbidden words. The golden-mean shift forbids 11:
fromsoficimportShiftOfFiniteTypesft=ShiftOfFiniteType.from_forbidden_words(
{("1", "1")},
symbol_alphabet=frozenset({"0", "1"}),
)
sft.validate()
sft.forbidden_words() # frozenset({('1', '1')})sorted(sft.factor_language(3)) # allowed length-3 wordssft.is_unifilar() # True (right-resolving presentation)Topological Markov chain — an adjacency-matrix presentation; compute the topological entropy or extract the measure of maximal entropy:
importnumpyasnpfromsoficimportTopologicalMarkovChaintmc=TopologicalMarkovChain.from_adjacency(
np.array([[1, 1], [1, 0]], dtype=float), # golden-mean adjacencysymbol_alphabet=frozenset({0, 1}),
)
tmc.validate()
tmc.topological_entropy() # 0.4812 (ln of the golden ratio)tmc.parry_measure() # MealyHMM at maximal entropySofic shift — a labeled-graph presentation (the shift-space analog of an
NFA). This is the even shift (even-length runs of 0 between 1s):
fromsoficimportSoficShifteven=SoficShift(symbol_alphabet=frozenset({0, 1}))
even.add_transition("even", "even", 0)
even.add_transition("even", "odd", 1)
even.add_transition("odd", "even", 1)
even.validate()
even.topological_entropy() # 0.4812The presentations are related by a web of conversions. Probabilistic models can drop their weights to become automata or shifts (keeping only their support); HMMs can be minimized to ε-machines; automata can be determinized, minimized, and turned into regular expressions:
# Between stochastic presentationsgm.to_mealy() # any HMM -> Mealy HMMmoore.to_mealy() # Moore -> Mealy (joint edge law)EpsilonMachine.from_hmm(gm) # HMM -> minimal causal ε-machineeps.to_bidirectional() # ε-machine -> bidirectional presentationeps.mixed_state_presentation() # -> observer belief-state dynamicsEpsilonMachine.from_time_reversed(eps) # forward -> reverse ε-machine# Stochastic -> topological (drop probabilities, keep the support)gm.to_sofic_shift() # HMM support as a sofic shiftgm.to_support_nfa() # HMM support as an NFAgm.to_support_dfa() # HMM support as a (determinized) DFA# Between automatanfa.determinize() # NFA -> DFADFA.from_nfa(nfa) # NFA -> DFA (same result)dfa.minimize() # DFA -> minimal DFAdfa.to_regex() # automaton -> regular expression# Between / out of shiftstmc.to_sofic_shift() # topological Markov chain -> sofic shifttmc.parry_measure() # shift -> max-entropy MealyHMMsofic.parry_measure() # sofic shift -> max-entropy MealyHMMEvery model can also be round-tripped through YAML:
text=eps.to_yaml()
restored=EpsilonMachine.from_yaml(text)
# or: sofic.model_to_yaml(eps) / sofic.model_from_yaml(text)With dit installed, a bidirectional ε-machine exposes the full stored- and
transient-information anatomy of a process (James, Burke & Crutchfield, 2013):
fromsofic.examplesimportgolden_mean_bidirectional, tent_map_misiurewicz_bidirectionalbidir=golden_mean_bidirectional(0.5)
bidir.statistical_complexity() # 1.5850 bits (C±)bidir.excess_entropy() # 0.2516 bits (E)bidir.crypticity() # 1.3333 bits (chi = C± - E)tent=tent_map_misiurewicz_bidirectional()
tent.information_anatomy() # {'rho_mu', 'bound_mu', 'ephemeral_mu',# 'entropy_rate', 'excess_entropy', 'crypticity'}sofic is distributed under the BSD 3-Clause License; see LICENSE.txt.