1.5k views
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
retagged | 1.5k views
If we convert any NFA to DFA is that the minimal DFA or the process is NFA -> DFA -> minimize the DFA
Minimal dfa is reducing the no of states of an Dfa

Check following NFA. I've done subset construction too. $8$ States are needed even after minimization..

Every state containing D is final state.

NFA:

NFA to DFA

 0 1 A A AB AB AC ABC AC AD ABD AD A AB ABC ACD ABCD ABD AC ABC ACD AD ABC ABCD ACD ABCD

Third symbol from the right is a '$1$'. So, we can also consider Myhill-Nerode theorem here. Intuitively we need to remember the last $3$ bits of the string each of which forms a different equivalence class as per Myhill-Nerode theorem as shown by the following table. Here, for any set of strings (in a row), we distinguishes only the rows above it - as the relation is symmetric. Further strings in the language and not in the language are distinguished separately as $\epsilon$ distinguishes them.

Last $3$ bits Distinguishing string In the language?
$1$ $000$   N
$2$ $001$ "$00$" - distinguishes from  strings in $1$. N
$3$ $010$ "$0$" - distinguishes from strings in $1$ and $2$. "$00$" distinguishes from strings in $4$. N
$4$ $011$ "$0$" - distinguishes from strings in $1$ and $2$. "$00$" distinguishes from strings in $3$. N
$5$ $100$   Y
$6$ $101$ "$00$" distinguishes from strings in $5$. Y
$7$ $110$ "$0$" distinguishes from strings in $5$ and "$00$" distinguishes from strings in $6$ Y
$8$ $111$ "$00$" distinguishes from strings in $5$ and $7$. "$0$" distinguishes from strings in $6$. Y

edited by
Subset construction algo does not always give minimal dfa.
Yup got it. Thank you.
any specific example?
@VS , Can you tell me where is it written that "subset construction algo does not always give minimal DFA" ? Is there any method which can directly give minimal DFA from NFA or do we have to check it anyway after applying any algo?

@Xylene

eg : (ooo+ooooo)*

Minimal nfa has= 5 states

DFA by subset construction = 13 states

Minimal DFA=9 states //In dfa obtained after subset construction if you check closely the last 5 states can be combined into a single state i.e. states 9 to 13 .

AFAIK there is no algo from which we could directly generate a minimal dfa

0's as inputs

btw we can find the minimal dfa using equivalence classes of states followed by transition table.
@Praveen sir

but,it is not easy to find equivalence classes always.
[ACD] on input 1 is going to [ABD] not in [ABC]. Kindly correct the answer.
It is easy to find equivalence class always. we can find minimum dfa also.

NFA =4 state

DFA = 8 state { A,AB,AC,AD,ABC,ABD,ACD,ABCD }

P.S Here { AD,ABD,ACD,ABCD} these are final states i forgot to circle them

is the above diagram accepting the string 1100???

To attempt these type of questions, the important thing is that since u are dealing with symbols from right when you consume string from the left u have to take care of all possible combinations

So the answer wil always be 2where n is the position from the right

And for position from left, it is n+1
–1 vote
b.
third symbol from right is 1..

bit setting from right so no trap/dead state..
total 4 states required..
reshown
8 states are needed ! (Even if you try to minimize)
i didnt understand, can sir  help?
Minimal no states in DFA : 8

no of states in NFA : 4
edited

4 states are enough for the language of all binary strings in which the third symbol from the right is a 1.

1

NO, you're wrong here, you can not draw DFA like this for this question it will not give all valid sequence

e.g  1100 ,1101, 1111,1110 etc

these all are binary strings in which the third symbol from the right is a 1.which you can not draw from your DFA .see my explanation i have uploaded a pic for better clarity.