DFA String Examples
Design a DFA in which set of all strings can be accepted which end with ‘a’.
Given: Input alphabet, Σ={a, b}
Language L ={aa, aba, aaabbba, 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 will first start accepting ‘b’ on start state itself and then on a we will go to final state.
- And on final state we do not care for a’s so we have to put a self-loop.
- On final state if ‘b’ comes then we will redirect it start state so that any string which does not end with ‘a’ should not get accepted.
Testing
- Lets take one input string baba
- 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 A
- Fourth input is a, so from state A we will go to state B(final state)