Automata

DFA String Examples


Design a DFA such that second sybmol from L.H.S. should be 'a'
Given: Input alphabet, Σ={a, b}
Language L = {aaa, aa, ba, aaaa, ba, ...}

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. From start either 'a' or 'b' can come so state A and state B
  2. Then second input is if 'a' then reach out to final state C
  3. On state C(final state) we can accept everything, that's why a loop
  4. On state B we if we have input 'b' then reject it as second symbol must be 'a'
  5. D is a dead state and on it we can accept everything

Testing

  1. Lets take one input string aab
  2. Scan string from left to right
  3. First input is a, so from state A we will go to state B
  4. Second input is a, so from state B we will go to state C
  5. Third input is b, 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.
You may also try some examples of strings to run over this DFA, and you will understand more