# DFA String Examples

Design a DFA such that:

L = {a

^{n}b

^{m}| n,m ≥ 1} Given: Input alphabet, Σ={a, b}

Language L = {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 make DFA for smallest string that is ab, so three states will A, B and C, C being final state
- Now 'a' come multiple times so we have to loop on state B. Cause 'a' will always come before 'b'
- At state C if b comes then we have to loop it
- If 'b' comes on state A then we have to reject it, direct the flow to state D(dead state)
- If 'a' comes on state C then we have to reject it, direct the flow to state D(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)**

*After end of the string we are at final state so string is accepted.*

**You may also try some examples of strings to run over this DFA, and you will understand more**