DFA String Examples
Design a DFA in which every 'a' should be followed by 'b'
Given: Input alphabet, Σ={a, b}
Language L = {ε, ab, abab, 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 for ε we will make the start sate as final state.
- If the start input comes 'a' then we should have one 'b' as the next input and we should reach final state, that is why state B and C
- Suppose after first input 'a' again 'a' came then we should reject it, that is why we have state D and on state D we do not care for either a or b
- Here D state is a dead state
Testing
- Lets take one input string abbab
- Scan string from left to right
- First input is a, so from state A we will go to state B
- Second input is b, so from state B we will go to state C
- Third input is b, so from state C we will go to state C itself
- Fourth input is a, so from state C we will go to state B
- Fifth input is b, so from state B we will go to state C(final state)
You may also try some examples of strings to run over this DFA, and you will understand more