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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ The GNFA is a finite automaton with regular expressions along the edges, instead of single symbols. On this site a summary is given under the name state removal method. This method is mostly equivalent to that of Arden, but I like the graphic notation of the relevant languages between states. You probably should not ask us about which method to study, but rather your instructor, if you have one. $\endgroup$– Hendrik JanApr 29, 2022 at 18:23
-
$\begingroup$ @HendrikJan Thank You for the link, i should have been clear in the op. What i meant was " is the result of GNFA and Arden method same", which i learned it is from your comment and the link Thank you again :) $\endgroup$– Pratik HadawaleApr 30, 2022 at 5:09
-
$\begingroup$ Thanks for the clarification. I have added a reference that explicitly compares methods for transforming automata into expressions in a new answer. $\endgroup$– Hendrik JanApr 30, 2022 at 10:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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).
answered Apr 30, 2022 at 10:26
-
1$\begingroup$ Perfect, This is what i wanted to know :) Appreciate it $\endgroup$ Apr 30, 2022 at 11:53