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.
State Name | State Notation | Final State |
A | eeNo | |
B | eoNo | |
C | ooYes | |
D | oeNo |
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
- Take string ababbbbabb and traverse from left to right, here #a = 3 and #b = 7
- from left first input is ‘a’ and start state ‘A’
- so from state A we will go to state D
- second input is ‘b’ and from D on b we will go to C
- third input is ‘a’ and from C on a we will go state B
- fourth input is ‘b’ and from B on b we will go to state A
- fifth input is ‘b’ and from A on b we will go to state B
- sixth input is ‘b’ and from B on b we will go to state A
- seventh input is ‘b’ and from A we will go state B
- eighth input is ‘a’ and from B we will go state C
- ninth input is ‘b’ and from state C we will go to state D
- tenth input is ‘b’ and from state D we will go to state B