class_docstr: A class implementing rewriting systems for `FpGroup`s.
  
  References
  ==========
  .. [1] Epstein, D., Holt, D. and Rees, S. (1991).
         The use of Knuth-Bendix methods to solve the word problem in automatic groups.
         Journal of Symbolic Computation, 12(4-5), pp.397-414.
  
  .. [2] GAP's Manual on its KBMAG package
         https://www.gap-system.org/Manuals/pkg/kbmag-1.5.3/doc/manual.pdf
class_docstr_tok: ["A","class","implementing","rewriting","systems","for","`","FpGroup","`","s",".","References","==========","..","[","1","]","Epstein",",","D.",",","Holt",",","D.","and","Rees",",","S.","(","1991",")",".","The","use","of","Knuth-Bendix","methods","to","solve","the","word","problem","in","automatic","groups",".","Journal","of","Symbolic","Computation",",","12","(","4-5",")",",","pp.397-414",".","..","[","2","]","GAP","'s","Manual","on","its","KBMAG","package","https",":","\/\/www.gap-system.org\/Manuals\/pkg\/kbmag-1.5.3\/doc\/manual.pdf"]
docstr: Add new states and transitions to the automaton.
  
  Summary:
  States corresponding to the new rules added to the system are computed and added to the automaton.
  Transitions in the previously added states are also modified if necessary.
  
  Arguments:
      rules (dictionary) -- Dictionary of the newly added rules.
docstr_tok: ["Add","new","states","and","transitions","to","the","automaton",".","Summary",":","States","corresponding","to","the","new","rules","added","to","the","system","are","computed","and","added","to","the","automaton",".","Transitions","in","the","previously","added","states","are","also","modified","if","necessary",".","Arguments",":","rules","(","dictionary",")","--","Dictionary","of","the","newly","added","rules","."]
code: def _add_to_automaton(self, rules):
      """
      Add new states and transitions to the automaton.
  
      Summary:
      States corresponding to the new rules added to the system are computed and added to the automaton.
      Transitions in the previously added states are also modified if necessary.
  
      Arguments:
          rules (dictionary) -- Dictionary of the newly added rules.
  
      """
      # Automaton variables
      automaton_alphabet = []
      proper_prefixes = {}
  
      # compute the inverses of all the new rules added
      all_rules = rules
      inverse_rules = self._compute_inverse_rules(all_rules)
      all_rules.update(inverse_rules)
  
      # Keep track of the accept_states.
      accept_states = []
  
      for rule in all_rules:
          # The symbols present in the new rules are the symbols to be verified at each state.
          # computes the automaton_alphabet, as the transitions solely depend upon the new states.
          automaton_alphabet += rule.letter_form_elm
          # Compute the proper prefixes for every rule.
          proper_prefixes[rule] = []
          letter_word_array = list(rule.letter_form_elm)
          len_letter_word_array = len(letter_word_array)
          for i in range(1, len_letter_word_array):
              letter_word_array[i] = (
                  letter_word_array[i - 1] * letter_word_array[i]
              )
              # Add accept states.
              elem = letter_word_array[i - 1]
              if elem not in self.reduction_automaton.states:
                  self.reduction_automaton.add_state(
                      elem, state_type="a"
                  )
                  accept_states.append(elem)
          proper_prefixes[rule] = letter_word_array
          # Check for overlaps between dead and accept states.
          if rule in accept_states:
              self.reduction_automaton.states[rule].state_type = "d"
              self.reduction_automaton.states[rule].rh_rule = all_rules[
                  rule
              ]
              accept_states.remove(rule)
          # Add dead states
          if rule not in self.reduction_automaton.states:
              self.reduction_automaton.add_state(
                  rule, state_type="d", rh_rule=all_rules[rule]
              )
  
      automaton_alphabet = set(automaton_alphabet)
  
      # Add new transitions for every state.
      for state in self.reduction_automaton.states:
          current_state_name = state
          current_state_type = self.reduction_automaton.states[
              state
          ].state_type
          # Transitions will be modified only when suffixes of the current_state
          # belongs to the proper_prefixes of the new rules.
          # The rest are ignored if they cannot lead to a dead state after a finite number of transisitons.
          if current_state_type == "s":
              for letter in automaton_alphabet:
                  if letter in self.reduction_automaton.states:
                      self.reduction_automaton.states[
                          state
                      ].add_transition(letter, letter)
                  else:
                      self.reduction_automaton.states[
                          state
                      ].add_transition(letter, current_state_name)
          elif current_state_type == "a":
              # Check if the transition to any new state in possible.
              for letter in automaton_alphabet:
                  _next = current_state_name * letter
                  while (
                      len(_next)
                      and _next not in self.reduction_automaton.states
                  ):
                      _next = _next.subword(1, len(_next))
                  if not len(_next):
                      _next = "start"
                  self.reduction_automaton.states[state].add_transition(
                      letter, _next
                  )
  
      # Add transitions for new states. All symbols used in the automaton are considered here.
      # Ignore this if `reduction_automaton.automaton_alphabet` = `automaton_alphabet`.
      if len(self.reduction_automaton.automaton_alphabet) != len(
          automaton_alphabet
      ):
          for state in accept_states:
              current_state_name = state
              for letter in self.reduction_automaton.automaton_alphabet:
                  _next = current_state_name * letter
                  while (
                      len(_next)
                      and _next not in self.reduction_automaton.states
                  ):
                      _next = _next.subword(1, len(_next))
                  if not len(_next):
                      _next = "start"
                  self.reduction_automaton.states[state].add_transition(
                      letter, _next
                  )
  
file_path: sympy/sympy/combinatorics/rewritingsystem.py
imports: from collections import deque
  from sympy.combinatorics.rewritingsystem_fsm import StateMachine
label_desc: Use image node_id 13 for calling the RewritingSystem obj's underlying member method code with example usage: obj._add_to_automaton(rules) without return types