minimal NFA

Question

what will be minimal nfa for starting with 00 and endind with 00 ?

Answer 1

Since the required finite automate is NFA, we do not need to worry much about the details. It's usually much easier to create an NFA as compared to a DFA.

Here is the required NFA, with 5 states and $q_4$ as the final state.

---

EDIT:

Above was my previous answer. Maybe some others think of same in their first attempt. But that's wrong. As Prateek mentioned that it does not accept 00 and 000.

So I tried to correct it. Then created the following automata, which at first looked correct to me:

But this one is also wrong, consider the string 0010100.

So, I thought instead let's simplify the question a bit. Let's create an NFA for strings that start and end with a 0. I came up with this:

Now modifying this for our original question:

Hope I am correct this time. :)

Comments

but sir this nfa can't generate 00 and 000 which are also in language

---

Yeah you are right. Thanks for pointing it out.
I updated my answer, please see if it's correct or not.
Thanks for this question.

---

yeah it is correct almost minimized dfa except trap state and thank u sir

but it became difficult to create nfa ,sometimes when i confuse in minimized dfa generally i construct nfa then dfa but in this case nfa already became difficult,so plz help me

thank u

---

Shai Simonson's lectures are good for TOC.