Automata

DFA String Examples


Design a DFA such that:
L = {anbm | n,m ≥ 0} Given: Input alphabet, Σ={a, b}
Language L = {ε, a, aa, aaa, b, bb, bbb,ab, aab, aaab, abbb, aabb, aaaabbbb, ...}

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. Firstly there is ε so make start state as final state
  2. If the first symbol 'a' comes then it should be accepted so loop it to start state
  3. When 'b' comes then direct the flow to state 'b' and then loop to 'b'
  4. If 'a' comes on state B then it should be rejected as there should not be any 'a' after 'b'
  5. Here state C is dead state

Testing

  1. Lets take one input string aaabbbb
  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 B itself
  5. Third input is a, so from state B we will go to state B itself
  6. Fourth input is b, so from state B we will go to state C(final state)
  7. Fifth input is b, so from state B we will go to state C(final state)
  8. Sixth input is b, so from state B we will go to state C(final state)
  9. Seventh input is b, so from state B we will go to state C(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




Quantitative Aptitude
Reasoning
Programming
Interview