19 views

I need help in understanding the reasoning behind finding total number of states when positions of particular input is fixed from left hand side or right hand side. The Gate Overflow website shows the formula that for:

1. nth position from the left side of the string is fixed , the number of states is  n+2
2. nth position from the right side of the string is fixed, the number of states is  2n

I want to understand the logic behind this generalized formula. How did we come to this conclusion?

closed with the note: Question has been answered previously on the main website.

closed ago | 19 views
+1
0
Firstly, thank you for sharing the link, I tried drawing certain DFA diagrams and understood for the case when nth position from the left side of the string is fixed , the number of states is  n+2.

But,

I could not deduce the same for the case when nth position from the right side of the string is fixed, the number of states is  2^n. Is there any way where you could show me via diagrams for certain number of n positions where we can generalize the concept of 2^n positions in DFA?
+1
Explainations are also provided, right ?
0
Yes, I found them in the "supported documents link" at the bottom of the post. I had overlooked that earlier. Thank you.