in Theory of Computation retagged by
9,352 views
37 votes
37 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?
in Theory of Computation retagged by
9.4k views

4 Comments

If we convert any NFA to DFA is that the minimal DFA or the process is NFA -> DFA -> minimize the DFA
6
6
Minimal dfa is reducing the no of states of an Dfa
0
0
what would be no of states after minimizing? I m getting 7. Is it correct?
0
0
conversion of NFA to DFA does not guarantee minimal DFA. For minimization of DFA, we have to apply M-H theorem.
0
0

9 Answers

1 vote
1 vote

# 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
1 vote
1 vote

...

–1 vote
–1 vote
b.
third symbol from right is 1..

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

2 Comments

edited by
8 states are needed ! (Even if you try to minimize)
0
0
i didnt understand, can sir  help?
0
0
–2 votes
–2 votes
Minimal no states in DFA : 8

no of states in NFA : 4
edited by

Related questions