The Gateway to Computer Science Excellence

+19 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**

$$\begin{array}{|l|l|l|}\hline \text{} & \text{0} & \text{1} \\\hline \text{A} & \text{A} & \text{AB} \\ \text{AB} & \text{AC} & \text{ABC} \\ \text{AC} & \text{AD} & \text{ABD}\\ \textbf{AD} & \text{A} & \text{AB} \\ \text{ABC} & \text{ACD} & \text{ABCD} \\ \textbf{ABD} & \text{AC} & \text{ABC} \\ \textbf{ACD} & \text{AD} & \text{ABD}\\ \textbf{ABCD} & \text{ACD} & \text{ABCD} \\\hline \end{array}$$

The 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 distinguish 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.

$$\begin{array}{|l|c|l|l|}\hline \text{} & \textbf{Last}\ \textbf{3}\ & \textbf{Distinguishing string} & \textbf{In L?}\\

&\textbf{bits}\\

\hline 1 & 000 & \text{} & \text{N} \\ \hline

2 & 001 & \text{$“00$" distinguishes from strings in $1$.} & \text{N} \\\hline

3 & 010 & \text{“$0$" distinguishes from strings in $1$ and $2$.} & \text{N} \\

&& \text{“$00$" distinguishes from strings in $4$.}\\\hline

4 & 011 & \text{“$0$" distinguishes from strings in $1$ and $2$.}& \text{N} \\

&&\text{“$00$" distinguishes from strings in $3$.}\\\hline

5 & 100 & \text{} & \text{Y} \\\hline

6 & 101 & \text{“$00$" distinguishes from strings in $5$.} & \text{Y} \\\hline

7 & 110 & \text{“$0$" distinguishes from strings in $5$.} & \text{Y}\\

&&\text{“$00$" distinguishes from strings in $6$.}\\\hline

8 & 111 & \text{“$00$" distinguishes from strings in $5$ and $7$.} & \text{Y}\\

&&\text{“$0$" distinguishes from strings in $6$.}\\\hline \end{array}$$

0

Well, it is more intuition. But rather I know the 8 classes from the question statement and just gave the distinguishing strings to show the classes. It is like imagining the minimal DFA, and finding the set of strings reaching each state of it.

+1

Strings in row 2 end in "001" and those in row one end in "000". Both these set of strings are not in L. Now, by appending "00", all the strings of row 2, now ends in "100" meaning they are now in $L$ while none of those in row 1 are in $L$ even after appending "00". That is the exact distinguishing string condition as per Myhill-Nerode theorem.

0

@arjun sir, Is it not always the case that after converting nfa to dfa (by subset construction method) we got minimized dfa? Do we need to check whether the dfa we got is minimized or not, by the procedure we used to convert the given dfa into minimal dfa.

0

@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?

+4

@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

+1

0

@anchitjindal07 this is bad case of subset construction for nfa to dfa I will recommend you refer hopcroft Ullman proof is difficult to understand but you will have an idea why it is so.

0

@Praveen Saini "Well in these questions, no of states in minimal Dfa is 2^n where n is position of specific symbol asked from last." Sir what if we have ternary string instead of binary? Will it be 3^n?

+14 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

+6 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

+3

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.

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.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,192 answers

193,988 comments

94,857 users