The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 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.

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 disntiguishes only the rows above it - as the relation is symmetric. Further strings in the language and not in the language are disntinguished separately as $\epsilon$ distinguishes them.

Last 3 bits | Distinguishing string | In the language? | |
---|---|---|---|

1 | 000 | N | |

2 | 001 | "00" - disntinguishes from strings in 1. | N |

3 | 010 | "0" - disntinguishes 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" disntinguishes 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.1k
- Engineering Mathematics 4.5k
- Digital Logic 1.9k
- Programming & DS 3.3k
- Algorithms 2.9k
- Theory of Computation 3.6k
- Compiler Design 1.4k
- Databases 2.7k
- CO & Architecture 2.4k
- Computer Networks 2.7k
- Non GATE 901
- Others 1.2k
- Admissions 246
- Exam Queries 433
- Tier 1 Placement Questions 17
- Job Queries 42
- Projects 4

32,330 questions

39,146 answers

108,246 comments

36,501 users