This paper investigates the necessary and sufficient graphical conditions for converting Galois nonlinear feedback shift registers (NLFSRs) into Fibonacci NLFSRs, aiming to provide theoretical support and a decision framework for the equivalence conversion between these two types of shift register structures. First, using the matrix semi-tensor product theory, the algebraic representations of the evolution equations for both Galois and Fibonacci NLFSRs are established, and then the algebraic criteria for their transformation are derived. Second, based on the state transition matrix of Fibonacci NLFSRs, the intrinsic state transfer properties are analyzed and a set partition method is introduced. Accordingly, graphical criteria for the transformation between the two types of NLFSRs are established. Furthermore, according to the proposed conversion conditions, a corresponding structural conversion algorithm is designed to realize the transformation from Galois to Fibonacci NLFSRs. Finally, two numerical examples are presented to verify the feasibility and effectiveness of the proposed criteria and the designed transformation algorithm.