# DFA String Examples

Design a DFA over w ∈ {a,b}

^{*}such that number of a = 2 and there is no restriction over length of b.

**Answer**

We will explain this intuitive approach

**Step 1**Make smallest string DFA:

Means for number of a’s = 2 , crate a DFA then in next step we will take care of b’s.

**Step 2**

Now we will take care of b’s

**You can test any string which has number of a’s = 2, will be accepted in the above.**

Design a DFA in which number of a’s in the string are ≥ 2

**Answer**

Like above we will create DFA taking care of number of a’s ≥ 2, and input alphabet is a, b

So in this way we will take care of the language, L = {aa, aab, baba, bbaa, aabb, …….}

It is pretty clear that language is infinite.

Design a DFA in which number of a’s in the string are ≤ 2

**Answer**

Like above we will create DFA taking care of number of a’s ≤ 2, and input alphabet is a, b

So in this way we will take care of the language, L = {∈ b, a, ab, bba, bba, abb, …….}

It is pretty clear that language is infinite.

#### Testing

- Take a string ‘ababb’ to test whether it is accepted in the above DFA
- Scan string from left to right
- first input we get is
**a**and from start state(A) on ‘a’ we go to B - second input is b, from state B on b we will go to state B itself.
- third input is a, from B we go to state C.
- from state C we go to state B on fourth input symbol C itself
- from C on fifth symbol b, we will go to state C itself.
- Now we reached end of string and we are standing on final state C.

#### Negative Testing

- Take a string ‘ababba’ to test whether it is accepted in the above DFA
- Scan string from left to right
- first input we get is
**a**and from start state(A) on ‘a’ we go to B - second input is b, from state B on b we will go to state B itself.
- third input is a, from B we go to state C.
- from state C we go to state B on fourth input symbol C itself
- from C on fifth symbol b, we will go to state C itself.
- from C on sixth symbol a, we will go to state D
- Now we reached end of string and we are
**not**standing on final state C.

Design a DFA in which number of a’s are divisible by 2. And input alphabet is {a,b}

**Answer**

And if you check any string in the language, L = {b, aab,aa, aaaab, aabbbbbbb, …… }, this DFA will accept it. And if the string do not follow the property will not be accepted.

In the similar ground we can create DFA in which number of a’s are divisible by 2 with remainder 1.

**Means ->**#a mod 2 =1