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.