Consider the Finite Automaton represented by the following table

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.

Leave a Reply

Your email address will not be published. Required fields are marked *