# Pfoof by induction

• Feb 3rd 2013, 06:43 AM
baxy77bax
Pfoof by induction
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 :

$\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 ??(Worried)

Thank you !!!!
baxy
• Feb 4th 2013, 09:30 AM
emakarov
Re: Pfoof by induction
You need a stronger induction statement. Namely, you need to define three predicates Ps, P1 and Pf on strings such that the following property holds:

For all strings w, Ps(w) is true iff w is accepted starting from qs, P1(w) is true iff w is accepted starting from q1, and Pf(w) is true iff w is accepted starting from qf. (*)

In particular, Ps(w) is defined to be true iff w has at least two 1's and ends with a 1. Then you prove (*) by induction on string length.