Automata

DFA String Examples


Design a DFA such a way that
Let string is w, Number of a(w) mod 2 != 0 and Number of b(w) mod 2 != 0. This means number of a should not be divisible by 2 as well as number of b should also not be divisible by 2.

Answer
If you see this question it is also just a bit variation of the above question.
The notations which we have used, we can choose which will be final state.
eeeooooe
State NameState NotationFinal State
ANo
BNo
CYes
DNo

Note As the requirement is either number_of_a(w) mod 2 = 0 or number_of_b(w) mod 2=0 or both.
That is the reason we are assigning multiple final states.

Testing

  1. Take string ababbbbabb and traverse from left to right, here #a = 3 and #b = 7
  2. from left first input is ‘a’ and start state ‘A’
  3. so from state A we will go to state D
  4. second input is ‘b’ and from D on b we will go to C
  5. third input is ‘a’ and from C on a we will go state B
  6. fourth input is ‘b’ and from B on b we will go to state A
  7. fifth input is ‘b’ and from A on b we will go to state B
  8. sixth input is ‘b’ and from B on b we will go to state A
  9. seventh input is ‘b’ and from A we will go state B
  10. eighth input is ‘a’ and from B we will go state C
  11. ninth input is ‘b’ and from state C we will go to state D
  12. tenth input is ‘b’ and from state D we will go to state B
After end of the string we are standing at state C, which is final state. So we say that string got accepted. There could be many variations of the above question, try to figure out them




Quantitative Aptitude
Reasoning
Programming
Interview