retagged by
13,363 views
40 votes
40 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?
retagged by

9 Answers

Best answer
37 votes
37 votes

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

edited by
20 votes
20 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

9 votes
9 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 

2 votes
2 votes

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

     

edited by

Related questions

21 votes
21 votes
5 answers
1
Arjun asked Nov 15, 2015
5,718 views
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
20 votes
20 votes
3 answers
2
Akash Kanase asked Apr 18, 2016
3,451 views
Consider the binary tree in the figure below:Give different steps for deleting the node with key $5$ so that the structure is preserved.