correct pda intersection, add more tests for union, concatenation and…

… kleene star
Aunsiels · bygu4 · Sep 28, 2024 · Sep 28, 2024 · Sep 29, 2024 · Sep 29, 2024
commit e4bf660b14264685ea23f3fb4c0e85420b27351d
diff --git a/pyformlang/finite_automaton/tests/test_epsilon_nfa.py b/pyformlang/finite_automaton/tests/test_epsilon_nfa.py
@@ -87,7  87,7 @@ def test_deterministic(self):
         assert not dfa.accepts([point])
         assert not dfa.accepts([plus])
 
-    def test_union(self):
     def test_union0(self):
         """ Tests the union of two epsilon NFA """
         enfa0 = get_enfa_example0()
         enfa1 = get_enfa_example1()
@@ -101,7  101,25 @@ def test_union(self):
         assert not enfa.accepts([symb_a])
         assert not enfa.accepts([])
 
-    def test_concatenate(self):
     def test_union1(self):
         """
         Tests the union of three ENFAs.
         Union is (a*b)|(ab )|c
         """
         enfa0 = get_enfa_example0()
         enfa1 = get_enfa_example1()
         enfa2 = get_enfa_example2()
         enfa = enfa0 | enfa2
         enfa |= enfa1
         accepted_words = list(enfa.get_accepted_words(3))
         assert ["b"] in accepted_words
         assert ["a", "b"] in accepted_words
         assert ["a", "a", "b"] in accepted_words
         assert ["a", "b", "b"] in accepted_words
         assert ["c"] in accepted_words
         assert len(accepted_words) == 5
 
     def test_concatenate0(self):
         """ Tests the concatenation of two epsilon NFA """
         enfa0 = get_enfa_example0()
         enfa1 = get_enfa_example1()
@@ -116,7  134,23 @@ def test_concatenate(self):
         assert not enfa.accepts([symb_b])
         assert not enfa.accepts([])
 
-    def test_kleene(self):
     def test_concatenate1(self):
         """
         Tests the concatenation of three ENFAs.
         Concatenation is a*bc((ab )|c)
         """
         enfa0 = get_enfa_example0()
         enfa1 = get_enfa_example1()
         enfa2 = get_enfa_example2()
         enfa = enfa0   enfa1
         enfa  = enfa2
         accepted_words = list(enfa.get_accepted_words(4))
         assert ["b", "c", "c"] in accepted_words
         assert ["a", "b", "c", "c"] in accepted_words
         assert ["b", "c", "a", "b"] in accepted_words
         assert len(accepted_words) == 3
 
     def test_kleene0(self):
         """ Tests the kleene star of an epsilon NFA """
         enfa0 = get_enfa_example0()
         symb_a = Symbol("a")
@@ -130,6  164,23 @@ def test_kleene(self):
         assert not enfa.accepts([symb_a])
         assert not enfa.accepts([symb_a, symb_b, symb_a])
 
     def test_kleene1(self):
         """
         Tests the kleene star of an ENFA.
         Expression is ((ab )|c)*
         """
         enfa = get_enfa_example2()
         enfa = enfa.kleene_star()
         accepted_words = list(enfa.get_accepted_words(3))
         assert [] in accepted_words
         assert ["a", "b"] in accepted_words
         assert ["a", "b", "b"] in accepted_words
         assert ["a", "b", "c"] in accepted_words
         assert ["c", "a", "b"] in accepted_words
         for i in range(3):
             assert ["c"] * (i   1) in accepted_words
         assert len(accepted_words) == 8
 
     def test_complement(self):
         """ Tests the complement operation """
         enfa = EpsilonNFA()
@@ -544,7  595,7 @@ def get_enfa_example0():
 
 
 def get_enfa_example1():
-    """ Gives and example ENFA
     """ Gives an example ENFA
     Accepts c
     """
     enfa1 = EpsilonNFA()
@@ -557,6  608,21 @@ def get_enfa_example1():
     return enfa1
 
 
 def get_enfa_example2():
     """ Gives an example ENFA
     Accepts (ab )|c
     """
     enfa = EpsilonNFA(start_states={0, 3},
                       final_states={2, 4})
     enfa.add_transitions([
         (0, "a", 1),
         (1, "b", 2),
         (2, "b", 2),
         (3, "c", 4),
     ])
     return enfa
 
 
 def get_enfa_example0_bis():
     """ A non minimal NFA, equivalent to example0 """
     enfa0 = EpsilonNFA()

diff --git a/pyformlang/pda/pda.py b/pyformlang/pda/pda.py
@@ -467,12  467,11 @@ def intersection(self, other: DeterministicFiniteAutomaton) -> "PDA":
             When intersecting with something else than a regex or a finite
             automaton
         """
-        start_state_other = other.start_states
-        if len(start_state_other) == 0:
         start_state_other = other.start_state
         if not start_state_other:
             return PDA()
         pda_state_converter = _PDAStateConverter(self._states, other.states)
-        start_state_other = list(start_state_other)[0]
-        final_state_other = other.final_states
         final_states_other = other.final_states
         start = pda_state_converter.to_pda_combined_state(self._start_state,
                                                           start_state_other)
         pda = PDA(start_state=start,
@@ -484,40  483,37 @@ def intersection(self, other: DeterministicFiniteAutomaton) -> "PDA":
         while to_process:
             state_in, state_dfa = to_process.pop()
             if (state_in in self._final_states and state_dfa in
-                    final_state_other):
                     final_states_other):
                 pda.add_final_state(
                     pda_state_converter.to_pda_combined_state(state_in,
                                                               state_dfa))
             for symbol in symbols:
                 if symbol == Epsilon():
                     symbol_dfa = finite_automaton.Epsilon()
                     next_state_dfa = state_dfa
                 else:
                     symbol_dfa = finite_automaton.Symbol(symbol.value)
-                if symbol == Epsilon():
-                    next_states_dfa = [state_dfa]
-                else:
-                    next_states_dfa = other(state_dfa, symbol_dfa)
-                if len(next_states_dfa) == 0:
                     next_state_dfa = other.get_next_state(state_dfa, symbol_dfa)
                 if not next_state_dfa:
                     continue
                 for stack_symbol in self._stack_alphabet:
                     next_states_self = self._transition_function(state_in,
                                                                  symbol,
                                                                  stack_symbol)
                     for next_state, next_stack in next_states_self:
-                        for next_state_dfa in next_states_dfa:
-                            pda.add_transition(
-                                pda_state_converter.to_pda_combined_state(
-                                    state_in,
-                                    state_dfa),
-                                symbol,
-                                stack_symbol,
-                                pda_state_converter.to_pda_combined_state(
-                                    next_state,
-                                    next_state_dfa),
-                                next_stack)
-                            if (next_state, next_state_dfa) not in processed:
-                                to_process.append((next_state, next_state_dfa))
-                                processed.add((next_state, next_state_dfa))
                         pda.add_transition(
                             pda_state_converter.to_pda_combined_state(
                                 state_in,
                                 state_dfa),
                             symbol,
                             stack_symbol,
                             pda_state_converter.to_pda_combined_state(
                                 next_state,
                                 next_state_dfa),
                             next_stack)
                         if (next_state, next_state_dfa) not in processed:
                             to_process.append((next_state, next_state_dfa))
                             processed.add((next_state, next_state_dfa))
         return pda
 
     def __and__(self, other: DeterministicFiniteAutomaton) -> "PDA":