DFA String Examples


Design a DFA in which set of all strings can be accepted which contain ab.
Given: Input alphabet, Σ={a, b}
Language L ={ab, aba, abaabbb, abba, bbabaabb ….}

Clearly the language is infinite because there is infinite number of strings. The idea behind this approach is very simple, follow the steps below and you will understand.

  1. First we will make DFA for accepting the smallest string that is ‘ab’ and after that whatever comes at final state we don’t care as the condition is satisfied.
  2. In DFA we have to take care of all the input alphabets at every state.
  3. so we have to take care of input symbol ‘b’ on state A, that is we made self-loop on start state.
  4. On state B if a comes then we will accept it as repetition of ‘a’ after a will not ruin anything . Because we want ab in the entire string anywhere.
  5. On state C for input a and b we do not care so we will make one self-loop for ‘a’, ‘b’

Testing

  1. Lets take one input string baababa
  2. First input is b, so from state A we will go to state A itself
  3. Second input is a, so from state A we will go to state B
  4. Third input is a, so from state B we will go to state B itself
  5. Fourth input is b, so from state B we will go to state C
  6. Fifth input is a, so from state C we will go to state C itself
  7. Sixth input is b, so from state C we will go to state C itself
  8. Seventh input is a, so from state C we will go to state C itself(final state)
After end of the string we are at final state so string is accepted.