Zephod is an educational and research-oriented Python framework for defining, simulating, visualizing, and exploring the theoretical foundations of computation through various automata models.
This framework provides a unified API to work with the classical hierarchy of computational models:
| Model | Power | Use Case |
|---|---|---|
| Finite Automata | Regular languages | Pattern matching, lexical analysis |
| Pushdown Automata | Context-free languages | Parsing, balanced structures |
| Turing Machines | Recursively enumerable languages | General computation |
-
Finite Automata (
zephod/finite.py)- Deterministic (DFA) and Non-deterministic (NFA) support
- Epsilon (ε) transitions with automatic closure computation
- Automatic NFA → DFA conversion (subset construction)
- DFA minimization (Hopcroft's algorithm)
- Regular expression composition via operators (
+,|,~for union, concatenation, and Kleene star) - Convert to equivalent grammar or pushdown automaton
-
Pushdown Automata (
zephod/pushdown.py)- Stack-based computation model
- Push, Pop, and Null stack operations
- Accept by final state
-
Turing Machines (
zephod/turing.py)- Multi-tape support
- Read, write, and bidirectional head movement
- Deterministic and non-deterministic machines
- Debug mode with step-by-step execution trace
-
Grammar Processing (
grammar.py)- Define grammars with production rules
- Enumerate strings up to a given length
- Build finite automata from regular grammars
- Build grammars from finite automata
-
Regular Language DSL (
regular.py)- Define regular languages using declarative rules:
Even(pattern)/Odd(pattern)— parity constraintsContained(pattern)/NotContained(pattern)— substring constraintsOrder(before, after)— symbol ordering constraints
- Automatically compiles rules into a minimal finite automaton
- Define regular languages using declarative rules:
-
Language Formulas (
formula.py)- Define context-sensitive languages using symbolic expressions
- Specify constraints with SymPy expressions (e.g.,
k > 0,Eq(m + n, k)) - Enumerate valid strings from the language
-
Turing Machine Builder (
builder.py)- Automatically generate Turing machines from language formulas
- Handles parsing, counting, and constraint verification
-
Function Machines (
function.py)- Define computable functions as Turing machines
- Input/output in unary representation
- Supports multi-variable arithmetic expressions
-
Planning System (
planner.py)- High-level plans for parsing and tape operations
- Accumulation, comparison, and arithmetic on tapes
- Graph visualization using Graphviz/pygraphviz
- LaTeX/TikZ export for publications
- CSV export for Turing machine transition tables
- Color-coded transitions by symbol
- Jupyter notebook integration
- Clone the repository:
git clone https://github.com/your-username/zephod.git
cd zephod- Install dependencies:
pip install -r requirements.txt- For visualization features, install Graphviz:
# Ubuntu/Debian
sudo apt install graphviz libgraphviz-dev
# macOS
brew install graphviz- Add the project to your Python path:
export PYTHONPATH="${PYTHONPATH}:/path/to/zephod"from zephod.finite import *
from utils.plotter import AutomataPlotter
# Define transitions
transition = FADelta()
transition.add("q0", "q0", {"0", "1"})
transition.add("q0", "q1", {"1"})
transition.add("q1", "q2", {"1"})
# Create the automaton
nfa = FiniteAutomata(transition, initial="q0", final={"q2"})
# Test a string
print(nfa.read("011")) # True
# Get the minimal DFA
dfa = nfa.minimal()
# Visualize
AutomataPlotter.plot(dfa)from zephod.finite import Z
# Build automaton from regex: (aaa)* | (bb)* | (cd)* + ab
regex = (~Z("aaa") | ~Z("bb") | (~Z("cd") + Z("ab"))).minimal()
print(regex.read("aaaaaabb")) # Truefrom zephod.pushdown import *
# PDA for palindromes with center marker: wcw^R
transition = PDADelta()
transition.add("q0", "q0", {
("a", Stack.EMPTY): Push(obj="A"),
("a", "A"): Push(obj="A"),
("b", Stack.EMPTY): Push(obj="B"),
("b", "B"): Push(obj="B"),
})
transition.add("q0", "q1", {("c", "A"): Null(), ("c", "B"): Null()})
transition.add("q1", "q1", {("a", "A"): Pop(), ("b", "B"): Pop()})
transition.add("q1", "q2", {("$", Stack.EMPTY): Null()})
pda = PushdownAutomata(transition, initial="q0", final={"q2"})
pda.debug("abcba")from zephod.turing import *
# Turing machine with 2 tapes
transition = TuringDelta(tapes=2)
transition.add("q0", "q1", {
T(0): A("a", move=Right()),
T(1): A(Tape.BLANK, new="X", move=Right())
})
tm = TuringMachine(initial="q0", final={"q1"}, transition=transition)
tm.debug("aaa")from utils.automaton.builder import TuringParser
from utils.language.formula import LanguageFormula
from sympy import symbols, Eq
a, b, c = symbols("a b c")
k, m = symbols("k m")
# Language: a^k b^m c^k where k > 0
lang = LanguageFormula(
expression=[a**k, b**m, c**k],
conditions=[k > 0, m >= 0]
)
# Automatically generate recognizing Turing machine
parser = TuringParser(language=lang)
parser.turing.debug("aabbbcc")from utils.automaton.function import FunctionMachine
from sympy import symbols
x, y = symbols("x y")
# f(x, y) = 3x + 2y
func = FunctionMachine(expression=3*x + 2*y, domain=[x >= 0, y >= 0])
func.run_machine({x: 2, y: 3}) # Computes 3*2 + 2*3 = 12The examples/ directory contains runnable demonstrations:
| File | Description |
|---|---|
finite-automata/nfsm-example.py |
NFA construction, minimization, and grammar extraction |
finite-automata/regular-expression.py |
Building automata from regex operators |
finite-automata/regular-language.py |
Declarative regular language definitions |
pushdown-automata/pda-example.py |
PDA for palindromes with center marker |
turing-machine/machine-example.py |
Manual Turing machine construction |
turing-machine/language-example.py |
Auto-generated TMs from language formulas |
turing-machine/function-example.py |
Computable arithmetic functions |
Run any example:
python examples/finite-automata/nfsm-example.pyzephod/
├── zephod/ # Core automata implementations
│ ├── automata/
│ │ ├── base.py # Base Automata class with graph building
│ │ ├── delta.py # Transition function and state management
│ │ └── tape.py # Tape, Buffer, Stack, and Input abstractions
│ ├── finite.py # Finite Automata (DFA/NFA)
│ ├── pushdown.py # Pushdown Automata
│ └── turing.py # Turing Machines
├── utils/
│ ├── automaton/
│ │ ├── builder.py # Turing machine generation from formulas
│ │ ├── function.py # Computable function machines
│ │ └── planner.py # Machine plan DSL
│ ├── language/
│ │ ├── formula.py # Language formulas with constraints
│ │ ├── grammar.py # Grammar processing
│ │ └── regular.py # Regular language DSL
│ └── plotter.py # Visualization utilities
├── examples/ # Runnable examples
└── requirements.txt # Python dependencies
- Learn automata theory with interactive simulations
- Visualize state machines and understand their structure
- Trace execution step-by-step with debug mode
- Convert between equivalent representations (NFA↔DFA, grammar↔automaton)
- Define complex languages using symbolic constraints
- Auto-generate Turing machines for language recognition
- Implement computable functions and verify their computation
- Export to LaTeX/TikZ for academic papers
- Prototype lexers/parsers using finite and pushdown automata
- Test language membership for formal language definitions
- Explore the Chomsky hierarchy with concrete implementations
- Define any finite automaton (deterministic or non-deterministic)
- Compose automata using regex operators
- Minimize DFAs automatically
- Build PDAs with arbitrary stack operations
- Create multi-tape Turing machines
- Generate TMs from declarative language specifications
- Compute arithmetic functions on unary inputs
- Enumerate strings from grammars and languages
- Turing machine generation works best for linear counting constraints
- Non-terminating computations require manual interruption
- No built-in support for alternating or probabilistic automata
- Context-sensitive grammar support is limited
MIT License - see LICENSE file for details.