DFA String Examples
Design a DFA in which set of all strings can be accepted which contains ‘a’.
Given: Input alphabet, Σ={a, b}
Language L = {a, ab, aaabbb, abba,baba ….}
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.
- We know that first input must be a and from start state on a we should go to final state, so two states are confirmed: start state and final state.
- And if the first input is b then we will loop it to the start state itself.
- Once we reach final state we accept everything that is why we have a loop
Testing
- Lets take one input string babab
- 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 B itself
- Fourth input is a, so from state B we will go to state B itself
- Fifth input is b, so from state B we will go to state B itself(final state)