Source code for pyformlang.finite_automaton.nondeterministic_finite_automaton

"""
Representation of a nondeterministic finite automaton
"""

from typing import Iterable

# pylint: disable=cyclic-import
from pyformlang.finite_automaton import epsilon

from .state import State
from .epsilon_nfa import EpsilonNFA
from .finite_automaton import to_symbol
from .symbol import Symbol
from .transition_function import InvalidEpsilonTransition


[docs]class NondeterministicFiniteAutomaton(EpsilonNFA): """ Represents a nondeterministic finite automaton This class represents a nondeterministic finite automaton, where epsilon \ transition are forbidden. Parameters ---------- states : set of :class:`~pyformlang.finite_automaton.State`, optional A finite set of states input_symbols : set of :class:`~pyformlang.finite_automaton.Symbol`, \ optional A finite set of input symbols transition_function : \ :class:`~pyformlang.finite_automaton.NondeterministicTransitionFunction`\ , optional Takes as arguments a state and an input symbol and returns a state. start_state : :class:`~pyformlang.finite_automaton.State`, optional A start state, element of states final_states : set of :class:`~pyformlang.finite_automaton.State`, optional A set of final or accepting states. It is a subset of states. Examples -------- >>> nfa = NondeterministicFiniteAutomaton() Creates the NFA. >>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)]) Adds two transitions. >>> nfa.add_start_state(0) Adds a start state. >>> nfa.add_final_state(1) Adds a final state. >>> nfa.accepts(["a"]) True >>> nfa.is_deterministic() False """
[docs] def accepts(self, word: Iterable[Symbol]) -> bool: """ Checks whether the nfa accepts a given word Parameters ---------- word : iterable of :class:`~pyformlang.finite_automaton.Symbol` A sequence of input symbols Returns ---------- is_accepted : bool Whether the word is accepted or not Examples -------- >>> nfa = NondeterministicFiniteAutomaton() >>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)]) >>> nfa.add_start_state(0) >>> nfa.add_final_state(1) >>> nfa.accepts(["a"]) True """ word = [to_symbol(x) for x in word] current_states = self._start_state for symbol in word: current_states = self._get_next_states_iterable(current_states, symbol) return any(self.is_final_state(x) for x in current_states)
[docs] def is_deterministic(self) -> bool: """ Checks whether an automaton is deterministic Returns ---------- is_deterministic : bool Whether the automaton is deterministic Examples -------- >>> nfa = NondeterministicFiniteAutomaton() >>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)]) >>> nfa.add_start_state(0) >>> nfa.add_final_state(1) >>> nfa.is_deterministic() False """ return len(self._start_state) <= 1 and \ self._transition_function.is_deterministic()
[docs] def to_deterministic(self) -> "DeterministicFiniteAutomaton": """ Transforms the nfa into a dfa Returns ---------- dfa : :class:`~pyformlang.deterministic_finite_automaton\ .DeterministicFiniteAutomaton` A dfa equivalent to the current nfa Examples -------- >>> nfa = NondeterministicFiniteAutomaton() >>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)]) >>> nfa.add_start_state(0) >>> nfa.add_final_state(1) >>> dfa = nfa.to_deterministic() >>> nfa.is_equivalent_to(dfa) True """ return self._to_deterministic_internal(False)
[docs] def add_transition(self, s_from: State, symb_by: Symbol, s_to: State) -> int: if symb_by == epsilon.Epsilon(): raise InvalidEpsilonTransition return super().add_transition(s_from, symb_by, s_to)