TOC

Question

Number of states in a DFA that accepts string over the alphabet {0,1} where words start and end with a 1, have even length and every 0 is immediately followed by atleast a 1.

Answer 1

TLDR : Answer is 5 states (along with 1 dead state)

Conditions are:

1. Starts and Ends with '1'

2. Even length

3. '0' is immediadetely followed by atleast a '1'

Sample strings :

11, 1011, 1101, 11011011

Please let me know if this is correct :)

Comments

It's correct!

But can't we have a edge from C to B on 0 rather than creating a new state D?
because that also accept the strings.

---

Then the string 110011 will be accepted. which violates the 3rd condition of the given problem.

So to eliminate this issue we just redirect it to another state (say D) instead of B.

I hope this helps :)

---

i think it should have 3 states, please correct me if i am wrong.