Python implementation of lstar automata learning algorithm.
Project description
L*
Implementation of the discriminant tree L* algorithm DFA learning algorithm provided in [^1].
Table of Contents
Installation
If you just need to use lstar
, you can just run:
$ pip install lstar
For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:
$ poetry install
Usage
The main entry point for using this library is the learn_dfa
function.
from lstar import learn_dfa
This function requires the arguments:
dfa = learn_dfa( inputs= .. , # Inputs over which the target concept is over. # Note: Sequence of Hashables. label=.., # Function answering whether a given word is in the target # language. # # Tuple[Alphabet] > bool find_counter_example=.., # Function which takes a hypothesis DFA # and either returns None or a counter example, # i.e., an element misclassified by hypothesis # DFA. # # DFA > Union[Tuple[Alphabet], None] )
Below is an example of learning following language over {0, 1}
:
The number of 1's in the word is a multiple of 4.
Label Queries
We start by defining the label query function.
Note that this implementation of lstar
assumes that this
function is either cheap (O(1)
ish) to call or is memoized.
from functools import lru_cache @lru_cache(maxsize=None) # Memoize member queries def is_mult_4(word): """Want to learn 4 state counter""" return (sum(word) % 4) == 0
Equivalence Queries
Next you need to define a function which given a candidate DFA
returns either a counter example that this DFA
mislabels or None
.
Note that the DFA
type used comes from the dfa
package
(link).
lstar
provides two functions to make writing counterexample oracles
easier.

validate_ce
: Takes a counterexample oracle and retries if returned "counterexample" is not actually a counterexample. Useful if using heuristic solver or asking a human.from lstar import validate_ce @validate_ce(is_mult_4, retry=True) def ask_human(dfa): ...

iterative_deeping_ce
: This function performs an iterative deepening traversal of the candidate dfa and see's if it matches the labeler on all tested words.from lstar import iterative_deeping_ce find_ce = iterative_deeping_ce(is_mult_4, depth=10)
All together
dfa = learn_dfa( inputs={0, 1}, # Possible inputs. label=is_mult_4, # Does this sequence belong in the language. find_counter_example=iterative_deeping_ce(is_mult_4, depth=10) ) assert not dfa.label(()) assert not dfa.label((1,)) assert not dfa.label((1, 1, )) assert dfa.label((1, 1, 1)) assert dfa.label((1, 1, 0, 1))
Learning Moore Machines and DFAlabelers
By default, learn_dfa
learns as Deterministic Finite Acceptor;
however, by specifying the outputs
parameter and adjusting the
label
function, one can learn a Deterministic Finite Labeler
(which is isomorphic to a Moore Machine).
For example, the 4 state counter from before can be modified to output the current count rather than whether or not the word sums to a multiple of 4.
def sum_mod_4(state): return sum(state) % 4 dfl = learn_dfa( inputs={0, 1}, label=sum_mod_4, find_counter_example=ask_human, outputs={0, 1, 2, 3}, ) # Returns a Deterministic Finite Labeler. assert dfl.label(()) == 0 assert dfl.label((1,)) == 1 assert dfl.label((1, 1, )) == 2 assert dfl.label((1, 1, 1)) == 3 assert dfl.label((1, 1, 0, 1)) == 3 assert dfl.label((1, 1, 1, 1)) == 0
The deterministic labeler can be interpreted as a moore machine by
using the transduce
method rather than label
.
assert dfl.transduce(()) == () assert dfl.transduce((1,)) == (0,) assert dfl.transduce((1, 1, )) == (0, 1) assert dfl.transduce((1, 1, 1)) == (0, 1, 2) assert dfl.transduce((1, 1, 0, 1)) == (0, 1, 2, 2) assert dfl.transduce((1, 1, 1, 1, 1)) == (0, 1, 2, 3, 0)
Testing
This project uses pytest. Simply run
$ poetry run pytest
in the root of the repository.
Similar Libraries
Python Based
1. https://github.com/steynvl/inferrer : DFA learning
library supporting active and passive dfa learning. Active
learning is based on L* with an observation table. Also
supports learning NFAs.

https://gitlab.lislab.fr/dev/scikitsplearn/ : Library for learning weighted automata via the spectral method.

https://pypi.org/project/pylstar/ : Another L* based DFA learning library.
Java Based
 https://learnlib.de/ : State of the art automata learning toolbox. Supports passive and active learning algorithms for DFAs, Mealy Machines, and Visibly Push Down Automata.
 https://github.com/lorisdanto/symbolicautomata : Library for symbolic automata and symbolic visibly pushdown automata.
Footnotes
[^1]: Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.