The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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?
asked in Theory of Computation by Veteran (52k points)
retagged by | 2.3k 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

6 Answers

+18 votes
Best answer


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

Every state containing D is final state. 




$$\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?}\\
\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}$$

answered by Boss (41k points)
edited by

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.

A mistake there !!

State ACD on input 1 will go to ABD instead of ABC


@tushar and @bad doctor.. now it is corrected :)

  Sir how this result of having 2^n states is derived?


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


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

+13 votes

NFA =4 state 


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

answered by Loyal (8.3k points)
is the above diagram accepting the string 1100???
I have a doubt in minimization process... can you please explain in detail how you are minimizing the DFA state transition table?Also this DFA is not accepting 1100.
Transition from ACD is to AD and not to A as shown in above diagram.

Minimized DFA accepts 1100 as A->AB->ABC->ACD->AD.
+5 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 2where n is the position from the right 

answered by Junior (555 points)
And for position from left, it is n+1

@eyeamgj why n+2?

–1 vote
third symbol from right is 1..

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

no of states in NFA : 4
answered by Active (2.7k points)
edited by
–2 votes

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


answered by Active (3.9k points)
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.

Related questions

+1 vote
0 answers
asked Sep 13, 2014 in CO & Architecture by Kathleen Veteran (52k points) | 208 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,540 questions
54,099 answers
71,007 users