**Question: Consider the Finite Automaton represented by the following table.**

**Prove, by induction on the string length, that this FA accepts every string in which a occurs an odd number of times.**

**Solution: **

The finite state diagram for above given is :

Here, 1 is the initial state and 2 is the final state

Now, for string **s = a**

from 1 we reach to 2 and our string is accepted

Now for string **s = aa**

form 1 we reach 2 and from 2 on a we reach 1 which is a non final state and hence the string is not accepted.

Now for string **s = aaa**

from 1 on a we reach 2, from 2 on a we reach 1 and form 1 on a we reach 2 and then our string gets accepted.

And so goes on.

So, we finally see that, on every odd occurence of a i.e 1, 3, 5, 7,9,….. our string gets accepted. and for every even occurence of a i.e 2, 4, 6,8,….our string is not accepted.

Hence, **through induction we have proved that this finite state accepts every odd occurrences of a as string.**