Learning of Context‐Free Grammars

AALpy supports the learning of visibly deterministic pushdown automata, which can be a subset of all context-free grammars.

Visibly deterministic pushdown automata

visibly refers to the fact that the user has to specify, in the alphabet, which symbols are internal, call, and return
call symbols push on the stack
return symbols pop from stack
internal symbols do not affect the stack
deterministic pushdown automata refers to the fact that the behavior of learned pushdown automata is deterministic, so it cannot, for example, learn languages like palindromes

In the following example, we demonstrate how to learn a model that can recognize regular expressions:

from aalpy.base import SUL
from aalpy.automata import SevpaAlphabet
from aalpy.oracles import RandomWordEqOracle
from aalpy.learning_algs import run_KV
import warnings
warnings.filterwarnings("ignore")

class ArithmeticSUL(SUL):
    def __init__(self):
        super().__init__()
        self.string_under_test = ''

    def pre(self):
        self.string_under_test = ''

    def post(self):
        pass

    def step(self, letter):
        if letter:
            self.string_under_test += ' ' + letter

        try:
            eval(self.string_under_test)
            return True
        except (SyntaxError, TypeError):
            return False

sul = ArithmeticSUL()

alphabet = SevpaAlphabet(internal_alphabet=['1', '+'], call_alphabet=['('], return_alphabet=[')'])

eq_oracle = RandomWordEqOracle(alphabet.get_merged_alphabet(), sul, min_walk_len=5,
                               max_walk_len=20, num_walks=20000)

learned_model = run_KV(alphabet, sul, eq_oracle, automaton_type='vpa')
learned_model.visualize()