aalpy.automata.Dfa

View Source
from aalpy.base import AutomatonState, DeterministicAutomaton


class DfaState(AutomatonState):
    """
    Single state of a deterministic finite automaton.
    """

    def __init__(self, state_id, is_accepting=False):
        super().__init__(state_id)
        self.is_accepting = is_accepting


class Dfa(DeterministicAutomaton):
    """
    Deterministic finite automaton.
    """

    def __init__(self, initial_state: DfaState, states):
        super().__init__(initial_state, states)

    def step(self, letter):
        """
        Args:

            letter: single input that is looked up in the transition table of the DfaState

        Returns:

            True if the reached state is an accepting state, False otherwise
        """
        if letter is not None:
            self.current_state = self.current_state.transitions[letter]
        return self.current_state.is_accepting

    def compute_characterization_set(self, char_set_init=None, online_suffix_closure=True, split_all_blocks=True):
        return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()],
                                                             online_suffix_closure,
                                                             split_all_blocks)
View Source
class DfaState(AutomatonState):
    """
    Single state of a deterministic finite automaton.
    """

    def __init__(self, state_id, is_accepting=False):
        super().__init__(state_id)
        self.is_accepting = is_accepting

Single state of a deterministic finite automaton.

#   DfaState(state_id, is_accepting=False)
View Source
    def __init__(self, state_id, is_accepting=False):
        super().__init__(state_id)
        self.is_accepting = is_accepting

Single state of an automaton. Each state consists of a state id, a dictionary of transitions, where the keys are inputs and the values are the corresponding target states, and a prefix that leads to the state from the initial state.

Args:

state_id(Any): used for graphical representation of the state. A good practice is to keep it unique.
View Source
class Dfa(DeterministicAutomaton):
    """
    Deterministic finite automaton.
    """

    def __init__(self, initial_state: DfaState, states):
        super().__init__(initial_state, states)

    def step(self, letter):
        """
        Args:

            letter: single input that is looked up in the transition table of the DfaState

        Returns:

            True if the reached state is an accepting state, False otherwise
        """
        if letter is not None:
            self.current_state = self.current_state.transitions[letter]
        return self.current_state.is_accepting

    def compute_characterization_set(self, char_set_init=None, online_suffix_closure=True, split_all_blocks=True):
        return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()],
                                                             online_suffix_closure,
                                                             split_all_blocks)

Deterministic finite automaton.

#   Dfa(initial_state: aalpy.automata.Dfa.DfaState, states)
View Source
    def __init__(self, initial_state: DfaState, states):
        super().__init__(initial_state, states)

Args:

initial_state (AutomatonState): initial state of the automaton
states (list) : list containing all states of the automaton
#   def step(self, letter):
View Source
    def step(self, letter):
        """
        Args:

            letter: single input that is looked up in the transition table of the DfaState

        Returns:

            True if the reached state is an accepting state, False otherwise
        """
        if letter is not None:
            self.current_state = self.current_state.transitions[letter]
        return self.current_state.is_accepting

Args:

letter: single input that is looked up in the transition table of the DfaState

Returns:

True if the reached state is an accepting state, False otherwise
#   def compute_characterization_set( self, char_set_init=None, online_suffix_closure=True, split_all_blocks=True ):
View Source
    def compute_characterization_set(self, char_set_init=None, online_suffix_closure=True, split_all_blocks=True):
        return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()],
                                                             online_suffix_closure,
                                                             split_all_blocks)

Computation of a characterization set, that is, a set of sequences that can distinguish all states in the automation. The implementation follows the approach for finding multiple preset diagnosing experiments described by Arthur Gill in "Introduction to the Theory of Finite State Machines". Some optional parameterized adaptations, e.g., for computing suffix-closed sets target the application in L*-based learning and conformance testing. The function only works for minimal automata. Args: char_set_init: a list of sequence that will be included in the characterization set, e.g., the input alphabet. A empty sequance is added to this list when using automata with state labels (DFA and Moore) online_suffix_closure: if true, ensures suffix closedness of the characterization set at every computation step split_all_blocks: if false, the computation follows the original tree-based strategy, where newly computed sequences are only checked on a subset of the states to be distinguished if true, sequences are used to distinguish all states, yielding a potentially smaller set, which is useful for conformance testing and learning

Returns: a characterization set