DFA String Examples
Design a DFA such that:
L = {anbm | n,m ≥ 0} Given: Input alphabet, Σ={a, b}
Language L = {ε, a, aa, aaa, b, bb, bbb,ab, aab, aaab, abbb, aabb, aaaabbbb, ...}
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 there is ε so make start state as final state
- If the first symbol 'a' comes then it should be accepted so loop it to start state
- When 'b' comes then direct the flow to state 'b' and then loop to 'b'
- If 'a' comes on state B then it should be rejected as there should not be any 'a' after 'b'
- Here state C is dead state
Testing
- Lets take one input string aaabbbb
- Scan string from left to right
- First input is a, so from state A we will go to state B
- Second input is a, 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 C(final state)
- Fifth input is b, so from state B we will go to state C(final state)
- Sixth input is b, so from state B we will go to state C(final state)
- Seventh 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