I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand one method of converting DFA to Regular Expression that is using Arden's Theorem. I assume GNFA is a medium between DFA and Regular Expression. Can someone explain the GNFA method? and also would i be okay not knowing it and only knowing the Arden Theorem method?
Jacques Sakarovitch studies the outcome of the various algorithms. See his paper The Language, the Expression, and the (Small) Automaton (CIAA 2005. LNCS 3845), where some results are summarized that are obtained in his book on automata theory. https://doi.org/10.1007/11605157_2
First one should note that the expression (and its size) highly depends on the order of handling the nodes, and not on the method.
When following strict methods (no additional tricks and shortcuts) the results seem syntactically equal. As far as I understand this result (from the paper) compares state elimination and Arden's solving equations.
Proposition 1. The state elimination method and the solution (by Gaussian elimination) of a system of linear equations taken from an automaton give the same regular expression (assuming that the same order in elimination is used in both cases).