MHB Convert a non-deterministic finite automata to a regular expression.

[JamesBwoii]

Hi, I'm trying to covert a NFA to a regular expression and I've manged to come up with an answer but I don't think that it is right.

Here's the question - http://i.imgur.com/NUHxTXY.png

And here's my workings - https://s3.amazonaws.com/pushbullet...DwoxqpvSFq3Fp4er00nEh/IMG_20141108_171450.jpg

Coming up with the final answer - a*ab(baUb)*b

I don't think that's correct though, and would appreciate any help.

Thanks.

 

[Evgeny.Makarov]

Hi, and welcome to the forum!

In the first image, you have an arrow labeled just be $b$ from the second state to the accepting state, but in the first automata in the second image, this arrow is labeled by $a,b$.

Also, which book or source describes the conversion procedure you are using?

 

[JamesBwoii]

Sorry, the first image is the correct one and the one I have drawn at the top of the page is a mistake.

As for the procedure it is a method that has been taught to us in lectures, although I could be misunderstanding it, here is how I take it:

Firstly, the NFA must be preprocessed such that:
1. Has a single final state.
2. Initial state does not have any incoming arrows.
3. Final state has no out going arrows.

As for the conversion algorithm, I will post a photo of my lecture notes as I feel that will represent it best - http://i.imgur.com/kbbVD1w.png

EDIT: I've managed to solve it now.