DFA String Examples
Design a DFA such that:
L = {anbmcl | n,m,l ≥ 1} Given: Input alphabet, Σ={a, b, c}
Language L = {abc, aabc, abbc, abcc, ...}
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.
- Accept the smallest string 'abc' in the DFA that is four states will be made and state D will be made the final state
- Now what if input 'b'/'c' comes on state A then it should be rejected as 'b'/'c' cannot come before 'a'
- At state B if 'a' comes then we can loop it as no given DFA property will be violated
- At state B if 'c' comes then it should be rejected as 'c' cannot come before 'b'
- At state C if 'b' comes then we will loop it
- At state C if 'a' comes then it should be rejected as 'a' cannot come after 'b'
- At state C if 'c' comes then it should flow to state D
- At state D if 'c' comes then we will loop it
- At state D if 'a'/'b' comes then it should be rejected as 'a'/'b' cannot come after 'c'
- State E will be Dead state and it will be looped for 'a', 'b' and 'c'
Testing
- Lets take one input string aaabbbcc
- 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
- Fifth input is b, 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 c, so from state C we will go to state D
- Eight 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