DFA String Examples
We will now discuss about string patterns such as, starting with some symbol, ending with some symbol, etc.
Design a DFA in which every 'a' should never followed by 'bb'Given: Input alphabet, Σ={a, b}
Language L = {ε, aa, bb, ab, aaa, bbbb, ...}
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.
- Firstly there is ε so make start state as final state
- And we do not care if string is only 'bbbbb...'(as this doesn't violate given property) so put self-loop on start state itself
- if a comes then we will move state B and we will make B as final state cause single 'a' also satisfy the property
- Here is trick part: if b comes after a we should accept it too, so C will be final state too
- And if 'a' comes at state C then we should direct it to state B as the property of DFA follows
- But if 'b' comes at state C then it should be rejected, and after that 'a' and 'b' doesn't bother
Testing
- Lets take one input string baba
- Scan string from left to right
- First input is b, so from state A we will go to state A itself
- Second input is a, so from state A we will go to state B
- Third input is b, so from state B we will go to state C
- Fourth input is a, so from state C we will go to state B(final state)
You may also try some examples of strings to run over this DFA, and you will understand more