pbt4automata 0.1.0

Property-based testing utilities for finite automata and context-free grammars.

pbt4automata

pbt4automata provides tools to construct finite automata and context-free grammars in Python and validate their behavior with property-based tests powered by Hypothesis.

Installation

pip install -e .

Examples

Deterministic Finite Automata

Testing a DFA against a rule

The following example tests a DFA that accepts all strings that contain the substring "010" or "100".

from pbt4automata import DFA

automaton = DFA(
    states=["q0", "q1", "q2", "q3", "q4", "q5"],
    alphabet="01",
    transition_function={
        ("q0", "0"): "q1",
        ("q0", "1"): "q4",
        ("q1", "0"): "q1",
        ("q1", "1"): "q2",
        ("q2", "0"): "q3",
        ("q2", "1"): "q4",
        ("q3", "0"): "q3",
        ("q3", "1"): "q3",
        ("q4", "0"): "q5",
        ("q4", "1"): "q4",
        ("q5", "0"): "q3",
        ("q5", "1"): "q2",
    },
    start_state="q0",
    accept_states=["q3"],
)

result = automaton.test("[01]*(010|100)[01]*")

if result is True:
    print("Success!")
else:
    print("Counterexample:", result)

You can also pass a function of type Callable[[str], bool] to automaton.test(...) instead of a regex.

Testing two DFAs for equivalence

from pbt4automata import Automaton, DFA

automata1 = DFA(
    ...
)

automata2 = DFA(
    ...
)

result = Automaton.test_equivalence(automata1, automata2)

if result is True:
    print("Success!")
else:
    print("Counterexample:", repr(result))

Context-Free Grammars

Testing a CFG against a rule

The following example tests a CFG in Chomsky Normal Form that generates all non-empty strings of balanced parentheses.

from pbt4automata import CNF

cnf = CNF(
    terminals="()",
    nonterminals="SLRX",
    productions={
        "S": ["LX", "SS"],
        "L": ["("],
        "R": [")"],
        "X": ["SR", ")"]
    },
    start_symbol="S"
)

def check_balance(input_string: str) -> bool:
    if input_string == "":
        return False
    s = 0
    for c in input_string:
        if c == "(":
            s += 1
        elif c == ")":
            s -= 1
        if s < 0:
            return False
    return s == 0

result = cnf.test(check_balance)

if result is True:
    print("Success!")
else:
    print("Counterexample:", result)

Development

Install dev dependencies and run tests:

pip install -e ".[dev]"
pytest -v