I'm not an expert, but I try to answer your question with an order, and if I will say something wrong, the people can improve my answer.
In general, is possible to use the State elimination method to convert a "Deterministic state automata" (DFA) to a regular expression (RE).
From the theory, we know the information below
If a language is regular, then it is described by a regular expression.
We also, know that if a language is regular is accepted by a DFA.
well now to convert a DFA that describes our regular language to the RE, we need to convert the DFA into a "Generalized Nondeterministic automata" (GNFA).
Definition of GNFA
A GNFA is simple nondeterministic finite automata (NFA) wherein the transition (arrows of the graph) can contain a regular expression.
We also need the rules about this GNFA, we need the rules below:
- The start state must behave only outgoing state and must hasn't incoming edge.
- The final/accepting state must have only incoming transition and it just hasn't outgoing edge.
We can convert easily DFA to a GNFA with a special form, with the following step:
- If a DFA has an incoming edge to the start state A, we move the start state to new state B and we can connect the state B->A with an empty string (ϵ).
In addition: The start state must have only outgoing transitions. (if there is an incoming arrow/edge, it must not carry a (non-empty) label).
- if the final/accepting state A has an outgoing transition, we can move the final state to a new state B and connect the node A->B with an empty string (ϵ).
In addition: The final/accepting state must have only incoming transitions.
PS. The additional informations are coming from the first comment below this answer.
Now the last step is to convert the GNFA to a RE.
After the conversion of DFA to a GNFA with a special form, we know that each arrow of GNFA can contain a regular expression, and at this point, the last step consists of the following passages:
- Remove the intermediate step with an intermedia regular expression, until to remove all intermediate state.
The result that we can have is
(InitState)--- RE---->(FinalState), and the regular expression of the transition from InitState to FinalState is the regular expression accepted from the previous DFA.
The passages can be express with the Figure below:
A complete example, that can help you to understand the process described inside this answer.