DFA String Examples
Design a DFA such that:
L = {anbmcl | n,m,l ≥ 0} Given: Input alphabet, Σ={a, b, c}
Language L = {ε, a, b, c, ab, abc, aabb, ...}
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.
- As there is ε we have to make start state as final state.
- If input is 'a' or multiple number of 'a' then we will loop it to start state itself A
- If 'b' comes then we will direct it to state B and loop it B state also for any number of 'b'
- From state B if input 'c' comes then it goes to state C and we will loop on C to accept any number of 'c'
- Now we will see all the inputs for every state
- For state A if c comes then yes it valid cause m ≥0. So flow goes to state directly C
- On state B if 'a' comes then it should get rejected as after 'b' 'a' cannot come. So flow goes to state D(dead state)
- On state C if 'a'/'b' come then it should get rejected as after 'c' input 'a'/'b' cannot come
- Like earlier we will loop for 'a', 'b' and 'c' on state D
Testing
- Lets take one input string aacc
- Scan string from left to right
- First input is a, so from state A we will go to state A itself
- Second input is a, so from state A we will go to state A itself
- Third input is c, so from state A we will go to state C
- Fourth input is c, 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