I am reviewing regular expressions and have been stuck on the following question:
Provide a regular expression to describe the language of the following NFA: NFA Diagram
I do not know how to answer the following question and I do not want someone to give me the answer to it. If possible, I'd greatly appreciate some guidance on how to either solve such questions or how to solve this particular problem. Thank you!
Any help is greatly appreciated!
The basic conversion, you know that.
{q0, x, q0} becomes x*
{q0, x, q1} becomes x
{q0, x, q1}, {q0, y, q1} becomes x+y
Your diagram is DFA.
Your right-most state should not be q1. You have double q1. Name the most right state q3 from now on.
I think the most difficult part is because there are outgoing transition from q3 back to q1 and q2.
We will start from the left part.
{q0, x, q0},{q0, y, q1} => x*y
q0 is start state, q1 is final state. Then x*y must always happen. The rest can happen or not, because there is transition back to q1 from q3. So, we can write like this:
RE = x*y( ... )*
We are working inside the brackets now.
{q1, x, q2}, {q1, y, q2} => (x+y)
Because there is a transition back to q2 from q3, we can write:
RE = x*y((x+y)( ... ))*
Because there is only one transition to reach final state i.e. {q3, y, q1}, then we put y at the last.
RE = x*y((x+y)( ... )y)*
The last part and the confusing part is {q2, y, q2}, {q2, x, q3}, {q3, x, q2} => (y+xx)*x
Explanation:
We are on q2 and we have y* or (xx)* one or more time to get back to q2. We can write (y*+(xx)*)* or simply (y+xx)*. Remember that we have to be on q3 to go to the final state by reading y, then from q2 we need to read x, so that (y+xx)*x.
So the complete regular expression: x*y((x+y)(y+xx)*xy)*