DFA String Examples
Design a DFA in which every 'a' should never followed by 'b'
Given: Input alphabet, Σ={a, b}
Language L = {ε, a, aa, aaa, 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.
- Firstly for ε we will make the start sate as final state.
- On start state if b comes then we will make self-loop as we are not violating the given property for DFA
- If the start input comes 'a' then that state should also final state. That is why state B is a final state
- On state B if b comes then that should be rejected, that is why state C
- On state B if a comes then that should be accepted
- On state C we do not care about either 'a' or 'b' that is why a self-loop
- Here C state is a dead state
Testing
- Lets take one input string baa
- 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 a, so from state B we will go to state B itself(final state)
You may also try some examples of strings to run over this DFA, and you will understand more