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_same_states=False, raise_warning=True): return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()], online_suffix_closure, split_all_blocks, return_same_states, raise_warning) def is_minimal(self): return self.compute_characterization_set(raise_warning=False) is not None def compute_output_seq(self, state, sequence): if not sequence: return [state.is_accepting] return super(Dfa, self).compute_output_seq(state, sequence) def to_state_setup(self): state_setup_dict = {} # ensure prefixes are computed self.compute_prefixes() sorted_states = sorted(self.states, key=lambda x: len(x.prefix)) for s in sorted_states: state_setup_dict[s.state_id] = (s.is_accepting, {k: v.state_id for k, v in s.transitions.items()}) return state_setup_dict
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.
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_same_states=False, raise_warning=True): return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()], online_suffix_closure, split_all_blocks, return_same_states, raise_warning) def is_minimal(self): return self.compute_characterization_set(raise_warning=False) is not None def compute_output_seq(self, state, sequence): if not sequence: return [state.is_accepting] return super(Dfa, self).compute_output_seq(state, sequence) def to_state_setup(self): state_setup_dict = {} # ensure prefixes are computed self.compute_prefixes() sorted_states = sorted(self.states, key=lambda x: len(x.prefix)) for s in sorted_states: state_setup_dict[s.state_id] = (s.is_accepting, {k: v.state_id for k, v in s.transitions.items()}) return state_setup_dict
Deterministic finite automaton.
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
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
View Source
def compute_characterization_set(self, char_set_init=None, online_suffix_closure=True, split_all_blocks=True, return_same_states=False, raise_warning=True): return super(Dfa, self).compute_characterization_set(char_set_init if char_set_init else [()], online_suffix_closure, split_all_blocks, return_same_states, raise_warning)
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 return_same_states: if True, a single distinguishable pair of states will be returned, or None None if there are no non-distinguishable states raise_warning: prints warning message if characterization set cannot be computed
Returns: a characterization set or None if a non-minimal automaton is passed to the function
View Source
def is_minimal(self): return self.compute_characterization_set(raise_warning=False) is not None
View Source
def compute_output_seq(self, state, sequence): if not sequence: return [state.is_accepting] return super(Dfa, self).compute_output_seq(state, sequence)
Given an input sequence, compute the output response from a given state. Args: state: state from which the output response shall be computed sequence: an input sequence over the alphabet
Returns: the output response
View Source
def to_state_setup(self): state_setup_dict = {} # ensure prefixes are computed self.compute_prefixes() sorted_states = sorted(self.states, key=lambda x: len(x.prefix)) for s in sorted_states: state_setup_dict[s.state_id] = (s.is_accepting, {k: v.state_id for k, v in s.transitions.items()}) return state_setup_dict