Metadata-Version: 2.4
Name: maquinas
Version: 0.4.0.0
Summary: Formal languages and automata library
Author-email: Ivan Vladimir Meza Ruiz <ivanvladimir+maquinas@gmail.com>
License: GNU General Public License v3 or later (GPLv3+) (GNU General Public License v3 or later)
Project-URL: Homepage, https://gitlab.com/ivanvladimir/maquinas
Keywords: regular languages,context free languages,context sensitive languages,recursively enumerable languages
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Education
Classifier: Topic :: Education
Classifier: License :: OSI Approved :: GNU General Public License v3 or later (GPLv3+)
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: graphviz
Requires-Dist: ipywidgets
Requires-Dist: IPython
Requires-Dist: ordered_set
Requires-Dist: Pillow
Requires-Dist: TatSu>=5.24.0
Requires-Dist: rich>=15.0.0
Requires-Dist: typer>=0.27.3
Requires-Dist: pyyaml>=6.0.3
Provides-Extra: dev
Requires-Dist: black; extra == "dev"
Requires-Dist: bumpver; extra == "dev"
Requires-Dist: isort; extra == "dev"
Requires-Dist: mypy>=2.4.0; extra == "dev"
Requires-Dist: pytest; extra == "dev"
Dynamic: license-file

<p align="center">
  <img src="https://gitlab.com/ivanvladimir/maquinas/-/raw/master/docs/source/_static/banner.svg" alt="maquinas — formal languages and automata in Python" width="100%">
</p>

<p align="center">
  <a href="https://pypi.org/project/maquinas/"><img src="https://img.shields.io/pypi/v/maquinas.svg" alt="PyPI"></a>
  <a href="https://pypi.org/project/maquinas/"><img src="https://img.shields.io/pypi/pyversions/maquinas.svg" alt="Python versions"></a>
  <a href="https://maquinas.readthedocs.io/"><img src="https://readthedocs.org/projects/maquinas/badge/?version=latest" alt="Documentation"></a>
  <a href="LICENSE"><img src="https://img.shields.io/badge/license-GPLv3%2B-blue.svg" alt="License: GPLv3+"></a>
</p>

**maquinas** is a Python library to build, run and visualize computing machines and
grammars. It is designed for teaching Formal Language Theory: define a machine as a
readable table, check which strings it accepts, and draw or animate it step by step.

| Language class          | Machines and grammars                                                        |
| ----------------------- | ---------------------------------------------------------------------------- |
| Regular                 | DFA, NDFA, NDFA-ε, regular expressions, regular grammars, minimization      |
| Context free            | Pushdown automata, context free grammars (Earley and CYK parsers)            |
| Context sensitive       | Linear bounded automata                                                      |
| Recursively enumerable  | Turing machines, two-stack pushdown automata                                 |

It also loads [JFLAP](https://www.jflap.org/) files, ships with the machines of the
JFLAP book as a ready-to-use collection, and has a command line tool.

## Installation

maquinas needs Python 3.12 or newer and [Graphviz](https://graphviz.org/download/)
for drawing (`apt install graphviz`, `brew install graphviz`, ...).

### With uv (recommended)

Add it to a [uv](https://docs.astral.sh/uv/) project:

```sh
uv init my-automata
cd my-automata
uv add maquinas
uv run python
```

Try the command line tool without installing anything:

```sh
uvx maquinas --help
```

Or install it as a tool, so `maquinas` is always on your `PATH`:

```sh
uv tool install maquinas
```

For notebooks, add Jupyter to the project and launch it:

```sh
uv add --dev jupyterlab
uv run jupyter lab
```

### With pip

```sh
python -m venv .venv
source .venv/bin/activate
pip install maquinas
```

## Quickstart

Write the transition table, load it and test some strings:

```python
from maquinas.io import load_fa

# Strings with an even number of a's
even_a = load_fa("""
         | a  | b  |
-> q0 ]  | q1 | q0 |
   q1    | q0 | q1 |
""")

even_a.accepts("abab")   # True
even_a.accepts("ab")     # False
even_a.print_summary()
```

In the table, `->` marks the initial state and `]` the accepting ones. Then look at it:

```python
even_a.draw()                               # display it in a notebook
even_a.save_image("even_a.png")             # save an image (.svg, .png, .pdf, ...)
even_a.save_animation("abab", "run.gif")    # animate it reading a string (.gif, .png, .webp)
even_a.save_animation("abab", "run.svg")    # or a small, vector animation
```

In a notebook, `Simulation(m, "abab").run()` (from `maquinas.simulation`) lets you
step through the run interactively.

## Examples

### Regular expressions

A regular expression becomes an equivalent NDFA-ε:

```python
from maquinas.regular.RE import RegularExpression as RE

r = RE("(a*ba*ba*)* + a*")    # an even number of b's
m = r.ndfa_e()
m.accepts("abba")             # True
m.accepts("ab")               # False
```

DFAs, NDFAs and NDFA-ε can also be built directly from their states and transitions:

```python
from maquinas.regular.dfa import DeterministicFiniteAutomaton as DFA

m = DFA(Q=["q_0", "q_1"], sigma=["a", "b"], q_0="q_0", A=["q_0"],
        delta=[(("q_0", "a"), "q_1"), (("q_0", "b"), "q_0"),
               (("q_1", "a"), "q_0"), (("q_1", "b"), "q_1")])
```

### Pushdown automata

Each cell lists transitions `pop/push→state`:

```python
from maquinas.io import load_pda

anbn = load_pda("""
       |     ε     |          a          |    b    |
->q_0  |           | Z₀/AZ₀→q_0,A/AA→q_0 | A/ε→q_1 |
  q_1  | Z₀/Z₀→q_2 |                     | A/ε→q_1 |
  q_2] |           |                     |         |
""")

anbn.accepts("aabb")   # True
anbn.accepts("aab")    # False
```

With one `pop/push` pair per stack, the same function loads a two-stack pushdown automaton,
which can recognize languages like aⁿbⁿcⁿ:

```python
anbncn = load_pda("""
        |        ε        |                a                 |      b      |       c       |
 ->q_0  |                 | Z₀/AZ₀,Z₀/AZ₀→q_0, A/AA,A/AA→q_0 | A/ε,A/A→q_1 |               |
   q_1  |                 |                                  | A/ε,A/A→q_1 | Z₀/Z₀,A/ε→q_2 |
   q_2  | Z₀/Z₀,Z₀/Z₀→q_3 |                                  |             | Z₀/Z₀,A/ε→q_2 |
   q_3] |                 |                                  |             |               |
""")

anbncn.accepts("aabbcc")   # True
```

### Turing machines and linear bounded automata

Each cell is `read/write→state:move` (`L`, `R` or `N`); `𝖁` is the blank:

```python
from maquinas.io import load_tm

anbn = """
        |     a     |     b     |     X     |     Y     |     𝖁     |
 ->q_0  | a/X→q_1:R |           |           | Y/Y→q_3:R |           |
   q_1  | a/a→q_1:R | b/Y→q_2:L |           | Y/Y→q_1:R |           |
   q_2  | a/a→q_2:L |           | X/X→q_0:R | Y/Y→q_2:L |           |
   q_3  |           |           |           | Y/Y→q_3:R | 𝖁/𝖁→q_4:L |
   q_4] |           |           |           |           |           |
"""

tm = load_tm(anbn)
tm.accepts("aabb")    # True

lba = load_tm(anbn, lba=True, most_left="left", sigma=["a", "b"])
lba.accepts("aabb")   # True
```

### Grammars and parsing

Context free grammars are parsed with Earley (default) or CYK, and their parse trees can
be drawn:

```python
from maquinas.contextfree.cfg import ContextFreeGrammar as CFG

g = CFG(r"""
E → E \+ T | T
T → T \* F | F
F → "id" | \( E \)
""")

g.accepts("id+id*id")                  # True
roots, chart, forest = g.parse("id+id*id")
g.print_chart("id+id*id")
trees = list(g.extract_trees(forest))
g.save_trees_img(trees, filename="tree")
```

Regular grammars work the same way:

```python
from maquinas.regular.rg import RegularGrammar as RG

g = RG("S → aS | bA; A → cA | ε")   # a*bc*
g.accepts("aabcc")                   # True
```

### Collections

The machines from the book *JFLAP: An Interactive Formal Languages and Automata Package*
(Rodger & Finley) come built in, each with sample strings it accepts and rejects:

```python
from maquinas.collections import jflap

jflap.names("regular")      # ['ex0.1a', 'ex1.1a', 'ex1.3a', ...]
m = jflap.load("ex1.1a")
m.metadata.accepted         # ['b', 'ab', 'aab', 'bbb', 'aaab']
```

Your own `.jff` files load with `maquinas.io.load_jflap`.

### Themes

Summaries, drawings and animations share color themes (ayu, catppuccin, gotham,
solarized and tender, each with a dark version):

```python
from maquinas.themes import set_theme

set_theme("catppuccin", dark=True)
```

## Command line

The `maquinas` command loads a machine, grammar or regular expression from a file (its
kind comes from the extension or `--type`):

```sh
maquinas even_a.fa summary                  # print the summary
maquinas even_a.fa accepts abab ab          # check strings (exit code 1 if any is rejected)
maquinas even_a.fa draw -o even_a.svg       # save an image
maquinas even_a.fa animate abab -o run.gif  # save an animation
maquinas even_a.fa                          # interactive shell
```

## Documentation

- Full documentation: <https://maquinas.readthedocs.io/>
- More examples: the [notebooks repository](https://github.com/ivanvladimir/maquinas_notebooks)

## Development

```sh
git clone https://gitlab.com/ivanvladimir/maquinas.git
cd maquinas
uv sync --extra dev
uv run pytest
```

Build the documentation with `uv run --group docs sphinx-build docs/source docs/build`.

## License

maquinas is distributed under the [GNU General Public License v3 or later](LICENSE).
