DFA..

Question

The minimum number of states required to construct a DFA that recognizes the language of string that recognizes the language of string over alphabet {0,1} whose 10th symbol from the right end is 1 is ____________

Comments

$2^{10}$??

---

I think it is 2¹⁰

---

how??

---

Try for 2nd symbol 1 from right,first NFA and then convert to DFA

DFA will not be minimized further.

---

I know that!!

Try to generalize it!

---

@ Ajay Jadhav

how do u know, it cannot be minimized further, without drawing DFA?

---

I drew for 2nd from right and 3rd from right,half states are final and half are non-final

Anyway what is the answer?

---

ans given, that  u told

Can u show me the DFA ?

---

See
last two symbols will be
00,01,10,11 among these we only want 10 and 11 so these are final
000,001,010,011,100,101,110,111(for 3rd symbol from right) among these 100,101,110,111 are useful
There is NPTEL lecture where this problem is discussed

---

have a look at this 

https://gateoverflow.in/63063/dfa

---

it cannot be minimized below 2¹⁰ because its goal is to remember sequence of all those possible 10 bits so for remembering those 10 bits we need 2¹⁰ states

---

https://www.youtube.com/watch?v=XxuH_K-wzpg watch till 10 mins 

also it cannot be minimized because every state is used for a unique 10bits

Answer 1

it cannot be minimized below 2¹⁰ because its goal is to remember sequence of all those possible 10 bits so for remembering those 10 bits we need 2¹⁰ states