[Solved]: Converting a NFA to its equivalent regular expression

Problem Detail: 

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions.

I have the following NFA:

I'm using the state elimination method to obtain the regular expression for the NFA. So I first introduced two new states, $q_{start}$ (the new start state of the NFA) and $q_{end}$ (the new and only accepting state of the NFA). After that, I eliminated the states one after the other.

To eliminate the states, I pick a state $p_e$ to be eliminated. Then for every pair $(p_1,p_2)$ with $p_1, p_2 \neq p_e$ and transitions from $p_1$ to $p_e$ and from $p_e$ to $p_2$, I determine the labels $r_0,r_1,r_2,r_3$ of this general automaton

wipe out $p_e$ and replace $(p_1,r_0,p_2)$ with $(p_1,r_0+r_1 r^{*}_2r_3,p_2)$.

I already eliminated states $q_0$ and $q_1$, but I have no idea how to eliminate state $q_4$, since it has no outgoing transitions except to itself. Could you please help me out with that?

Asked By : Javiator

Answered By : Hendrik Jan

Technically it can be reduced, by introducing a regular expression for the empty set, which represents the missing edge.

However, $q_4$ is completely useless for the language. They can be dropped without changing the accepted language. That should save some work.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42474

3.2K people like this

 Download Related Notes/Documents