Hi,

I need some help with the following problem. It is a cs problem so i don't quite know if this is the right place to post it but ...

Ok so what i have is a Finite State Automata :

$\displaystyle \sum=\{1,0\} \\ Q = \{q_{s},q_{1},q_{f}\} \\ q_{s} - start \\ q_{f} - final\\\delta:Q\times\sum \rightarrow Q : transition function$

and it looks like this :

Code:

0 0 1
+--+ +--+ +--+
| | | | | |
-+ 1 -+ 1
qs----------->q1----------------->qf
^ |
+-------------------+
0

This particular FSA accepts when given a string w=x1,x2,....xn, string has more then 2 1's and the last element is 1.

Now i don't know how to write dove the proof. I know that i need to show that there is a base case and then prove the induction step, but since this is not an example that i have seen before i don't know how to proceede. Can anyone help and write down the proof for this particular example ??

Thank you !!!!

baxy