DFA String Examples


Design a DFA in which set of all strings can be accepted which contains ‘a’.
Given: Input alphabet, Σ={a, b}
Language L = {a, ab, aaabbb, abba,baba ….}

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. We know that first input must be a and from start state on a we should go to final state, so two states are confirmed: start state and final state.
  2. And if the first input is b then we will loop it to the start state itself.
  3. Once we reach final state we accept everything that is why we have a loop

Testing

  1. Lets take one input string babab
  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 b, so from state B we will go to state B itself
  5. Fourth input is a, so from state B we will go to state B itself
  6. Fifth input is b, so from state B we will go to state B itself(final state)
After end of the string we are at final state so string is accepted.