The following state diagram depicts a DFA that recognizes th

The following state diagram depicts a DFA that recognizes the following language: {omega | omega contains at least three 1s} the alphabet is {0, 1} Formally prove that the state diagram above is correct. That is, prove that the computation on the automaton for all strings omega element {0, 1}* at contain at least 3 \'1\'s ends in an accept state, while computation on all other strings ends in one of the non-accept states. You can use induction or other proof techniques that you find suitable, except for coding.

Solution

Initially the automton is in the initial state such that q0 .

Standing in the state q0 two things can happen such that -

   case 1 - the automaton can read zero or more 0\'s and remains stuck in the state q0
  
   case 2 - the automaton can read a 1 and change its state from q0 to q1
  
   whenever case 2 happens and the automaton goes to state q1 , it never returns to state q0 .
  
   Till now, the automaton have read a string of zero or more 0\'s and followed by a single 1
  
   As q1 is not an accepting state this string will not be accepted by the automaton.
  
Standing in the state q1 two things can happen such that -

   case 1 - the automaton can read zero or more 0\'s and remains stuck in the state q1
  
   case 2 - the automaton can read a 1 and change its state from q1 to q2
  
   whenever case 2 happens and the automaton goes to state q2 , it never returns to state q1 .
  
   Till now, the automaton have read a string of zero or more 0\'s and two 1\'s
  
   As q2 is not an accepting state this string will not be accepted by the automaton.
  
Similarly, standing in the state q2 two things can happen such that -

   case 1 - the automaton can read zero or more 0\'s and remains stuck in the state q2
  
   case 2 - the automaton can read a 1 and change its state from q2 to q3
  
   whenever case 2 happens and the automaton goes to state q3 , it never returns to state q3 .
  
   Till now, the automaton have read a string of zero or more 0\'s and three 1\'s
  
   As q3 is the accepting state this string will be accepted by the automaton.
   Thus, a string having atleast three 1\'s and any number of 0\'s is accepted by the automaton. [proved]
  
Now, after reaching state q3 can read any number of 0\'s and 1\'s and this string also be accepted by the automaton
and this string contains atleast three 1\'s.