VPL* — Learning Visibly Pushdown Languages from Black-Box Acceptors

An open-source implementation of the VPL* framework of Barbot, Bollig, Finkel et al. for learning Visibly Pushdown Languages (VPLs) — and the context-free grammars underlying them — from a black-box string acceptor, by reducing the problem to learning a regular tree automaton with TL*.

The learner treats the target purely as a function T : Σ* → {0,1}: it never inspects the target's internals, only its accept/reject answers. This makes it applicable to any binary acceptor over a visibly pushdown alphabet — hand-written oracles, but also neural networks, transformers, and LLM wrappers.

This repository accompanies the MSc thesis Active Learning of Context-Free Grammars from Neural Networks via Tree-Automata (Juan Pedro da Silva, Universidad ORT Uruguay). Beyond re-implementing VPL*, it adds:

• a black-box, PAC-guaranteed equivalence oracle that samples trees (confidence/error bounds δ/ε), so no white-box access to the target is required;
• a study of the BParse membership gate — the A/B/C tree partition and three membership-query policies (gated, raw, hybrid) — together with a leakage detector that quantifies how far a target is from being a VPL.

The VPL-extraction idea itself is due to Barbot et al.; this repository re-implements and extends it.

Requirements

• Python 3.10+ (the code uses X | None type-hint syntax).
• No third-party dependencies — standard library only.

Installation

git clone <your-repo-url> vpl-learning
cd vpl-learning
python -m unittest discover -s tests   # optional: run the test suite

Run commands from the repository root so the package imports resolve.

Project structure

base/                       Core data structures
  alphabet.py                 VPAlphabet (push/pop/internal), RankedAlphabet
  tree.py                     Tree, Context, tree symbols
  vpl.py                      VPL — abstract string-acceptor interface
  vpl_star_comparator.py      Equivalence-query (comparator) interface
tree_automata/              Deterministic tree automata
  tree_automata.py            DTA + bottom-up run
  tree_generator.py           Random tree sampler
  tree_comparator.py          Sample-based tree-automaton comparison
  tree_state.py               States and transition keys
tree_automata_extraction/   TL* (tree learner)
  observation_table.py        Observation table + counterexample handling
  tl_star.py                  TL* main loop
vpl_extraction/             VPL* (the VPL learner on top of TL*)
  vpl_star.py                 VPLStar entry point
  vpl_star_oracle.py          Membership-query policies: gated / raw / hybrid
  pac_comparator.py           PAC equivalence oracle over trees + leakage collection
  vpl_star_random_comparator.py   Random-sampling comparator
  vpl_star_set_comparator.py      Fixed counterexample-set comparator
  leakage_detector.py         Leakage witnesses + Hoeffding report
models/                     Output models
  vpg.py                      Grammar extraction (nta2vpg) from a learned DTA
  tree_automata_vpl.py        Wrap a learned DTA as a string acceptor
  vpa.py, ...
utils/                      Encoding + gate
  encoding.py                 tree <-> sequence (seq / seq^-1), well-formedness
  b_parse.py                  The BParse gate automaton over T(BParse)
  well_formed.py              Well-formedness checks
  non_bparse_sampler.py       Malformation-stratified sampler for leakage probes
examples/                   Ready-made targets
  barbot_paper_examples.py    L(X,Y), RE-Dyck, Dyck-n, Alternating, ...
  dyck1.py                    Dyck-1 (balanced parentheses)
tests/                      Unit tests

Quickstart

Learn a target VPL and extract its grammar:

from examples.barbot_paper_examples import L_X_Y
from vpl_extraction.vpl_star import VPLStar
from vpl_extraction.pac_comparator import PACComparator
from models.vpg import vpg_from_tree_automata

# L(X, Y): every push symbol must precede every pop symbol.
# Use the push/pop letters a/b (the thesis convention).
target = L_X_Y(push_symbols={"a"}, pop_symbols={"b"}, internal_symbols=set())

# PAC equivalence oracle: each equivalence query is correct within (epsilon, delta).
comparator = PACComparator(target.alphabet, epsilon=5e-4, delta=5e-4, max_depth=6)

learner = VPLStar(target, comparator, policy="gated")
learned = learner.learn()            # -> a TreeAutomataVPL (wraps the learned DTA)

dta = learned.tree_automaton
grammar = vpg_from_tree_automata(dta, target.alphabet)
print(grammar.print_grammar())

learned is itself a string acceptor: learned.is_accepted("aabb") runs the learned automaton on a sequence.

Tighter epsilon/delta reduce the chance the PAC oracle terminates on a hypothesis that still disagrees with the target on rarely-sampled trees. The guarantee is per equivalence query.

Membership-query policies

Every membership query lifts the target through the tree-to-sequence map seq and classifies the queried tree against T(BParse), the set of well-formed (BParse-shaped) trees:

• Class A — tree in T(BParse): answer with the target on seq(t).
• Class B — tree not in T(BParse) but seq(t) is well-formed: a duplicate of the class-A tree with the same yield.
• Class C — tree not in T(BParse) and seq(t) not well-formed: the only place where a non-VPL target can leak (accept an ill-matched word).

Three policies decide what to answer off T(BParse):

Policy	Class A	Class B	Class C
gated	T(seq(t))	False	False
raw	T(seq(t))	T(seq(t))	T(seq(t))
hybrid	T(seq(t))	False	T(seq(t))

gated is the original VPL* policy (Barbot et al.). On a genuine VPL the three agree; they diverge only when the target leaks on class C. raw and hybrid both recover the correct grammar — they are equally valid, with no clear preference on a black-box target; their cost differs target-dependently.

from vpl_extraction.vpl_star_oracle import GATED, RAW, HYBRID

learner = VPLStar(target, comparator, policy=RAW)   # or GATED / HYBRID

Leakage detection

A leakage witness is a sequence w outside BParse with T(w) = 1. A single witness refutes "the target is a VPL over this alphabet." The PAC comparator samples ill-matched words (stratified by malformation type) on every equivalence query and accumulates a report:

learner = VPLStar(target, comparator, policy="gated")
learner.learn()

report = learner.get_leakage_report()
print(report.summary())
print("VPL-consistent:", report.is_vpl_consistent)   # True == no witness found

Absence of witnesses is weaker than their presence: the probes are not uniform over Σ* \ BParse, so "no witness found" is evidence, not proof, of VPL-ness.

Defining your own target

Any binary acceptor over a visibly pushdown alphabet can be learned. Subclass VPL and implement is_accepted:

from base.vpl import VPL
from base.alphabet import VPAlphabet

class BalancedAB(VPL):
    def __init__(self):
        super().__init__(VPAlphabet(push_symbols={"a"}, pop_symbols={"b"},
                                    int_symbols=set(), name="ab"))

    def is_accepted(self, sequence: str) -> bool:
        depth = 0
        for c in sequence:
            depth += 1 if c == "a" else -1
            if depth < 0:
                return False
        return depth == 0

Wrapping a neural network, transformer, or LLM is the same shape: implement is_accepted(sequence) -> bool around the model's decision. Those wrappers pull in extra dependencies and are kept out of this core library.

Running the tests

python -m unittest discover -s tests

Citation

If you use this code, please cite the thesis:

Juan Pedro da Silva. Active Learning of Context-Free Grammars from Neural Networks via Tree-Automata. MSc thesis, Universidad ORT Uruguay.

The framework it builds on:

R. Barbot, B. Bollig, A. Finkel, et al. Learning Visibly Pushdown Languages.

License

MIT — see LICENSE.