DFA String Examples
Design a DFA in which set of all strings can be accepted which contain ab.
Given: Input alphabet, Σ={a, b}
Language L ={ab, aba, abaabbb, abba, bbabaabb ….}
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.
- First we will make DFA for accepting the smallest string that is ‘ab’ and after that whatever comes at final state we don’t care as the condition is satisfied.
- In DFA we have to take care of all the input alphabets at every state.
- so we have to take care of input symbol ‘b’ on state A, that is we made self-loop on start state.
- On state B if a comes then we will accept it as repetition of ‘a’ after a will not ruin anything . Because we want ab in the entire string anywhere.
- On state C for input a and b we do not care so we will make one self-loop for ‘a’, ‘b’
Testing
- Lets take one input string baababa
- 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 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
- Fifth input is a, so from state C we will go to state C itself
- Sixth input is b, so from state C we will go to state C itself
- Seventh input is a, so from state C we will go to state C itself(final state)