For each state Apq which is a known terminal, this function
        searches for rules Apr -> Apq Aqr and Arq -> Arp Apq where
        Aqr is also a known terminal or Arp is also a known terminal.
        It is mainly used as an optimization in order to avoid the O(n^3)
        for generating all the Apq -> Apr Arq rules during the PDA to CFG
        procedure.
        Args:
            myntr (str): The examined non terminal that was poped out
                        of the queue
            maxstate (int): The maxstate is used for generating in a
                            dynamic way the CNF rules that were not
                            included due to the optimization. As a
                            result, the algorithm generates these
                            rules only if required.
        Returns:
            bool: Returns true if the algorithm was applied
                at least one time

def _check_intemediate(self, myntr, maxstate):
        """
        For each state Apq which is a known terminal, this function
        searches for rules Apr -> Apq Aqr and Arq -> Arp Apq where
        Aqr is also a known terminal or Arp is also a known terminal.
        It is mainly used as an optimization in order to avoid the O(n^3)
        for generating all the Apq -> Apr Arq rules during the PDA to CFG
        procedure.
        Args:
            myntr (str): The examined non terminal that was poped out
                        of the queue
            maxstate (int): The maxstate is used for generating in a
                            dynamic way the CNF rules that were not
                            included due to the optimization. As a
                            result, the algorithm generates these
                            rules only if required.
        Returns:
            bool: Returns true if the algorithm was applied
                at least one time
        """
        # print 'BFS Dictionary Update - Intermediate'
        x_term = myntr.rfind('@')
        y_term = myntr.rfind('A')
        if y_term > x_term:
            x_term = y_term
        ids = myntr[x_term + 1:].split(',')
        if len(ids) < 2:
            return 0
        i = ids[0]
        j = ids[1]
        r = 0
        find = 0
        while r < maxstate:
            if r != i and r != j:
                if 'A' + i + ',' + \
                        repr(r) not in self.resolved \
                        and 'A' + j + ',' + repr(r) in self.resolved:
                    self.resolved[
                        'A' + i + ',' + repr(r)] = self.resolved[myntr] \
                                                   + self.resolved['A' + j + ',' + repr(r)]
                    if self._checkfinal('A' + i + ',' + repr(r)):
                        return self.resolved['A' + i + ',' + repr(r)]
                    if 'A' + i + ',' + repr(r) not in self.bfs_queue:
                        self.bfs_queue.append('A' + i + ',' + repr(r))
                    find = 1
                if 'A' + repr(r) + ',' + j not in self.resolved and 'A' + \
                        repr(r) + ',' + i in self.resolved:
                    self.resolved[
                        'A' + repr(r) + ',' + j] = self.resolved['A' + repr(r) + ',' + i] \
                                                   + self.resolved[myntr]
                    if self._checkfinal('A' + repr(r) + ',' + j):
                        return self.resolved['A' + repr(r) + ',' + j]
                    if 'A' + repr(r) + ',' + j not in self.bfs_queue:
                        self.bfs_queue.append('A' + repr(r) + ',' + j)
                    find = 1
            r = r + 1
        if find == 1:
            return 1
        return 0