3
$\begingroup$

I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".

In other words, what is the general idea, and what is the difference to convert the NFA to RE and DFA to RE.

Online there are a lot of resources, but it is difficult to find a complete answer to understand the general idea of this method.

And, again, sorry if my question is too general, but I think that this place is a good place to meet people that understand this argument better than me, and are also able to explain it in a logical way.

Improve this question
$\endgroup$
0
2
$\begingroup$

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.

Structure example

enter image description here

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:

enter image description here

A complete example, that can help you to understand the process described inside this answer.

enter image description here

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I'd suggest • The start state must have only outgoing transitions. (if there is an incoming arrow/edge, it must not carry a (non-empty) label). and • The final/accepting state must have only incoming transitions. $\endgroup$ – greybeard Sep 26 '20 at 17:27
  • $\begingroup$ Thanks for this suggestion, I'm making the change $\endgroup$ – vincenzopalazzo Sep 26 '20 at 18:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.