The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 votes

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?

+13 votes

Best answer

Answer :-

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 |

@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

+9 votes

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

+2 votes

The answer is 8

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 2^{n }where n is the position from the right

–1 vote

b.

third symbol from right is 1..

bit setting from right so no trap/dead state..

total 4 states required..

third symbol from right is 1..

bit setting from right so no trap/dead state..

total 4 states required..

–2 votes

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

1

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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,846 answers

115,882 comments

39,703 users