|
1 | 1 | """ A general finite automaton representation """ |
2 | 2 |
|
3 | | -fromtypingimportList,Iterable,Any |
| 3 | +fromtypingimportList,Iterable,Set,Any |
4 | 4 |
|
5 | 5 | importnetworkxasnx |
6 | 6 | fromnetworkx.drawing.nx_pydotimportwrite_dot |
@@ -42,7 +42,6 @@ def __init__(self): |
42 | 42 | self._transition_function=None |
43 | 43 | self._start_state=set() |
44 | 44 | self._final_states=set() |
45 | | -self.__transitive_closure=None |
46 | 45 |
|
47 | 46 | defadd_transition(self,s_from:State,symb_by:Symbol, |
48 | 47 | s_to:State)->int: |
@@ -602,42 +601,55 @@ def get_accepted_words(self, max_length: int = -1) \ |
602 | 601 | """ |
603 | 602 | states_to_visit= [(start_state, []) |
604 | 603 | forstart_stateinself.start_states] |
605 | | -self.__set_transitive_closure() |
| 604 | +states_leading_to_final=self._get_states_leading_to_final() |
606 | 605 | whilestates_to_visit: |
607 | 606 | current_state,current_word=states_to_visit.pop(0) |
608 | 607 | iflen(current_word)>max_lengthandmax_length!=-1: |
609 | 608 | continue |
610 | 609 | transitions=self._transition_function.get_transitions_from( |
611 | 610 | current_state) |
612 | 611 | forsymbol,next_stateintransitions: |
613 | | -ifself.__exists_any_final_path_from(next_state): |
| 612 | +ifsymbol==Epsilon()andnext_state==current_state: |
| 613 | +continue |
| 614 | +ifnext_stateinstates_leading_to_final: |
614 | 615 | temp_word=current_word.copy() |
615 | 616 | ifsymbol!=Epsilon(): |
616 | 617 | temp_word.append(symbol) |
617 | 618 | states_to_visit.append((next_state,temp_word)) |
618 | 619 | ifself.is_final_state(current_state): |
619 | 620 | yieldcurrent_word |
620 | 621 |
|
621 | | -def__set_transitive_closure(self): |
| 622 | +def_get_states_leading_to_final(self)->Set[State]: |
622 | 623 | """ |
623 | | -Bulds MultiDiGraph transitive closure\ |
624 | | - ofFA and sets it to the private field. |
| 624 | +Gets a set of states from which one |
| 625 | + ofthe final states can be reached. |
625 | 626 | """ |
626 | | -self.__transitive_closure=nx.transitive_closure( |
627 | | -self.to_networkx()) |
628 | | - |
629 | | -def__exists_any_final_path_from(self,source:State)->bool: |
630 | | -""" |
631 | | - Checks if there are any paths from\ |
632 | | - given state to one of the final states. |
633 | | - """ |
634 | | -returnany(self.__exists_path(source,final) |
635 | | -forfinalinself.final_states) |
636 | | - |
637 | | -def__exists_path(self,source:State,target:State)->bool: |
638 | | -""" Checks if the target state can be reached from the source state """ |
639 | | -returntarget==sourceor \ |
640 | | -targetinself.__transitive_closure[source].keys() |
| 627 | +leading_to_final=self.final_states.copy() |
| 628 | +visited=set() |
| 629 | +states_to_process= [(None,start_state) |
| 630 | +forstart_stateinself.start_states] |
| 631 | +whilestates_to_process: |
| 632 | +previous_state,current_state=states_to_process.pop() |
| 633 | +ifprevious_stateandcurrent_stateinleading_to_final: |
| 634 | +leading_to_final.add(previous_state) |
| 635 | +continue |
| 636 | +ifcurrent_stateinvisited: |
| 637 | +continue |
| 638 | +visited.add(current_state) |
| 639 | +next_states=self._get_next_states_from(current_state) |
| 640 | +ifnext_states: |
| 641 | +states_to_process.append((previous_state,current_state)) |
| 642 | +fornext_stateinnext_states: |
| 643 | +states_to_process.append((current_state,next_state)) |
| 644 | +returnleading_to_final |
| 645 | + |
| 646 | +def_get_next_states_from(self,state_from:State)->Set[State]: |
| 647 | +""" Gets a set of states that are next to the given one """ |
| 648 | +next_states=set() |
| 649 | +for_,next_statein \ |
| 650 | +self._transition_function.get_transitions_from(state_from): |
| 651 | +next_states.add(next_state) |
| 652 | +returnnext_states |
641 | 653 |
|
642 | 654 | defto_deterministic(self): |
643 | 655 | """ Turns the automaton into a deterministic one""" |
|