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 set of all strings can be accepted which start with a.Given: Input alphabet, Σ={a, b}
Language L = {a, ab, aba, aabb, aaabbba, …..}
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 something else than ‘a’ then string should not be accepted. And we don’t care whatever comes on state C as state C now will work as dead state.
- Once we reach final state we accept everything that is why we have a loop
Testing
- Lets take one input string abab
- 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 B itself
- Third input is a, so from state B we will go to state B itself
- Fourth input is b, so from state B we will go to state B itself(final state)