DFA String Examples
Design a DFA such that second sybmol from L.H.S. should be 'a'
Given: Input alphabet, Σ={a, b}
Language L = {aaa, aa, ba, aaaa, ba, ...}
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.
- From start either 'a' or 'b' can come so state A and state B
- Then second input is if 'a' then reach out to final state C
- On state C(final state) we can accept everything, that's why a loop
- On state B we if we have input 'b' then reject it as second symbol must be 'a'
- D is a dead state and on it we can accept everything
Testing
- Lets take one input string aab
- 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 C
- Third input is b, so from state C we will go to state C itself(final state)
You may also try some examples of strings to run over this DFA, and you will understand more