6,654 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?

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
what would be no of states after minimizing? I m getting 7. Is it correct?

### Subscribe to GO Classes for GATE CSE 2022

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 the 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 the 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}$$

Distinguishing string column above plz explain how "00" - disntinguishes from  strings in 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.
@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.
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.

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?

No, it is not.

actually it is as $1+\left ( 2^0+2^1+2^2+.. \right )$ so it comes as $1+2^n-1 = 2^n$

but in case of ternary, it will go as $1+\left ( 3^0+3^1+3^2+... \right )$ so it is $1+\left ( 3^n-1 \right )/(3-1) \ne3^n$

https://www.geeksforgeeks.org/dfa-of-a-string-in-which-3rd-symbol-from-rhs-is-a/
We definitely know the DFA formed will consist of 8 states, but it can  be minimized to 7 states using equivalence method. So is the final answer 7 or 8?

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???
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.
Correction is needed in diagram

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
IT IS N+2

@eyeamgj why n+2?

# Consturct directly the minimized DFA without using NFA using basic method.

1. STEP 1: First construct skeleton of DFA to accept the smallest/Basic strings of language i.e. {100,101,110,111} . So states  {q3,q4,q6,q7} will be our Final-states which accepts above basic strings independently. These 4 states leads to the specific patterns which should be observed in step 2.

2.  STEP 2: To make it valid DFA ,still we need to show the transitions from final sates q3,q4,q6,q7. It is very easy to step the transitions further from these final states by considering strings which passes through these states, on both symbols {0,1} (like we do in DFAs). Keep in mind that every transition from final states will indicate for specific pattern which are drawn in step-1. Eg: q3 on 1 should go to q1 ,since on 1001, last 1 may become 3rd 1 from RHS (eg in 100100). hence choose transitions appropriately by observing previous patterns. Below is final minimized DFA. Let L be the language in which the third symbol from the right is a. Give a non-deterministic finite automaton that recognizes L. Third input symbol is a while reading the input symbol from RHS

$(a's\ or\ b's)\ a\fbox{aa}$

$(a's\ or\ b's)\ a\fbox{ab}$

$(a's\ or\ b's)\ a\fbox{ba}$

$(a's\ or\ b's)\ a\fbox{bb}$ Firstly try to draw 4 states namely $aaa,aab,aba,abb$ from the initial state and name the intermediate states along with it.

Now in-order to find out what are the transitions for $aaa,aab,aba,abb$ you can do the following:

$aaa \overset{b}{\rightarrow} a\fbox{aab}$

$aaa \overset{a}{\rightarrow} a\fbox{aaa}$

$aba \overset{b}{\rightarrow} a\fbox{bab}$

$aba \overset{a}{\rightarrow} a\fbox{baa}$

.

.

$\&\ likewise$

### 1 comment

What are the steps followed to conclude state bbb as an initial state? In general, how to choose an initial state for these kinds of problems?

b.
third symbol from right is 1..

bit setting from right so no trap/dead state..
total 4 states required..

edited
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

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

### 1 comment

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.