regexp_learner.lstar package

Submodules

regexp_learner.lstar.automaton_match module

automaton_match(g1: Automaton, g2: Automaton, verbose=False) → str

Tests whether two minimized deterministic Automaton recognize the same language. One can minimize an Automaton using pybgl.hopcroft_minimize.hopcroft_minimize.

Parameters:

• g1 (Automaton) – A minimal deterministic Automaton instance.

• g2 (Automaton) – A minimal deterministic Automaton instance.

• verbose (bool) – Pass True to print useful HTML information.

Returns:

None if g1 matches g2, otherwise a counter-example (possibly the empty word).

regexp_learner.lstar.learner module

class Learner(teacher: Teacher, epsilon: str = '', verbose: bool = True)

Bases: object

The learner (in the Angluin framework).

Constructor.

Parameters:

• teacher (Teacher) – The teacher aka oracle (in the Angluin framework).

• epsilon (str) – The empty word.

• verbose (bool) –

extend()

Extends the LstarObservationTable of this Learner. This method is triggered when the Teacher returns a counter example.

initialize(verbose: bool = True)

Initializes the LstarObservationTable of this Learner.

Parameters:

verbose (bool) – Pass True to print useful HTML information.

learn(verbose: bool = False) → Automaton

Trains the Learner to infer the Automaton of the Teacher.

Parameters:

verbose (bool) – Pass True to print useful HTML information.

Returns:

The inferred Automaton instance.

make_automaton_from_observation_table(o: LstarObservationTable, verbose: bool = False) → Automaton

Builds an Automaton instance from an LstarObservationTable instance.

Parameters:

• o (LstarObservationTable) – An LstarObservationTable instance.

• verbose (bool) –

Returns:

The resulting Automaton instance.

regexp_learner.lstar.observation_table module

class LstarObservationTable(a='abcdefghijklmnopqrstuvwxyz')

Bases: object

LstarObservationTable implements the L* observation table used by the Learner in the Angluin algorithm.

Constructor.

Args:

add_col()

Inserts a column in this LstarObservationTable.

add_prefix(s: str) → tuple

Inserts a prefix in this LstarObservationTable.

Parameters:

s (str) – The inserted prefix.

Returns:

• i is the index of s in this LstarObservationTable

• added equals True if s was not yet in this LstarObservationTable, False otherwise.

Return type:

A (i, added) tuple where

add_row()

Inserts a row in this LstarObservationTable.

add_suffix(e: str) → tuple

Inserts a suffix in this LstarObservationTable.

Parameters:

e (str) – The inserted suffix.

Returns:

• i is the index of e in this LstarObservationTable

• added equals True if e was not yet in this LstarObservationTable, False otherwise.

Return type:

A (i, added) tuple where

property e: set

Retrieves the observed suffixes.

Returns:

The set of suffixes observed in this LstarObservationTable.

find_mismatch_closeness() → tuple

Search a pair (prefix, symbol) that shows this LstarObservationTable is not closed.

Returns:

• s is a prefix of this LstarObservationTable;

• a is a symbol of the alphabet of this LstarObservationTable (i.e., self.a)

Return type:

A (s, a) pair (if found), None otherwise, where

find_mismatch_consistency() → tuple

Search a pair (prefix, symbol) that shows this LstarObservationTable is not closed.

Returns:

• s1 and s2 are two prefixes of this LstarObservationTable;

• a is a symbol of the alphabet of this LstarObservationTable (i.e., self.a)

• e is a contradicting suffix w.r.t. s1 and s2.

Return type:

A (s1, s2, a, e) pair (if found), None otherwise, where

get(s: str, e: str) → bool

Probes this LstarObservationTable for a given prefix and a given suffix.

Parameters:

• s (str) – The prefix.

• e (str) – The suffix.

Returns:

The observation related to s + e.

get_col(e: str) → int

Retrieves the column index related to a given prefix. See also LstarObservationTable.col().

Parameters:

e (str) – A suffix.

Returns:

The corresponding column if found, None otherwise.

static get_or_create_index(m: dict, k: str) → int

Retrieves the index of a key in a dictionary. If the key is not in the dictionary, the key is inserted and mapped with len(m).

Parameters:

• m (dict) – The dictionary.

• k (str) – The key.

Returns:

The index assigned to k.

get_row(s: str) → int

Retrieves the row index related to a given prefix. See also LstarObservationTable.row().

Parameters:

s (str) – A prefix.

Returns:

The corresponding row if found, None otherwise.

is_closed(verbose: bool = False) → bool

Checks whether this LstarObservationTable is closed (see Angluin’s paper or Angluin.pdf in this repository).

Parameters:

verbose (bool) – Pass True to print debug information.

Returns:

True if this LstarObservationTable is closed, False otherwise.

is_consistent(verbose: bool = False) → bool

Checks whether this LstarObservationTable is consistent (see Angluin’s paper or Angluin.pdf in this repository).

Parameters:

verbose (bool) – Pass True to print debug information.

Returns:

True if this LstarObservationTable is closed, False otherwise.

row(s: str) → bytes

Retrieves the row in this LstarObservationTable.

Parameters:

s (str) – A prefix.

Returns:

The corresponding row.

set(s: str, e: str, accepted: bool = True)

Fill this LstarObservationTable according to a given prefix, a given suffix, and a boolean indicating whether their concatenation belongs to the Teacher’s language.

Parameters:

• s (str) – The prefix.

• e (str) – The suffix.

• accepted (bool) – Pass True if s + e belongs to the Teacher’s language, False otherwise.

to_html() → str

Exports this LstarObservationTable to HTML.

Returns:

The corresponding HTML string.

regexp_learner.lstar.teacher module

class Teacher(g: Automaton)

Bases: object

The Teacher class (aka oracle) in the Angluin framework.

Constructor.

Parameters:

g – The pybgl.Automaton that the Learner tries to infer.

property alphabet: set

Accessor the alphabet of this Teacher instance.

Returns:

The alphabet of the pybgl.Automaton of this Teacher instance.

conjecture(h: Automaton) → str

Handles a conjecture query. (see Angluin’s paper or Angluin.pdf in this repository).

Parameters:

h (Automaton) – The tested pybgl.Automaton (typically, submitted by the Learner).

Returns:

True if h matches the Automaton of this Teacher instance, False otherwise.

membership_query(w: str) → bool

Handles a membership query. (see Angluin’s paper or Angluin.pdf in this repository).

Parameters:

w – The tested word (typically, submitted by the Learner).

Returns:

True if w is matched by the Automaton of this Teacher instance, False otherwise.

Module contents