Hi,

I am trying to convert an NFA related to language L(a*b*a) to DFA.



Somebody please guide me.



Zulfi.

 

The first thing you need is an NFA that actually recognizes the language you are working with.

Does your NFA accept "baa"? Should it?

 

You are right, thanks. I am correcting it.

Zulfi.

 

Hi,

I think this time its correct.

Zulfi.

 

Do we have to guess what the start state is?

Assuming it's the one in the upper left, does it accept the string "a"?

How hard is it to try out a handful of simple strings when you design a machine?

What purpose does the lower path to the accept state serve? What string does it accept that the upper path doesn't?

 

Hi,
Right. q0 is the initial state and q4 is the final state. Actually when I was trying to convert NFA to DFA , I was getting problems so I have to do that. But at this point if I make q4 as the final state then DFA can accept 'a' also. So lower part can help to accept string 'a'.

Is it okay?
Zulfi.

 

Hi,
Right. q0 is the initial state and q4 is the final state. Actually when I was trying to convert NFA to DFA , I was getting problems so I have to do that. But at this point if I make q4 as the final state then DFA can accept 'a' also. So lower part can help to accept string 'a'.

Is it okay?
Zulfi.

Do you mean that q0 was the start state and q1 was the original accept state and now you are making q4 an accept state as well?

It looks like it accepts the desired language now, although it is certainly a mess with paths that I'm pretty sure don't do what you think they do. But it is an NFA that appears to accept that language, so you can work with it.

 

Can you show me a better one?

Zulfi.

 

This one is perfectly fine for what you say you are trying to do, which is to convert an NFA to a DFA.