Results 1 to 2 of 2

Math Help - Pfoof by induction

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    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 ??


    Thank you !!!!
    baxy
    Last edited by baxy77bax; February 3rd 2013 at 05:46 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 17th 2008, 05:05 PM
  5. Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 5th 2007, 04:22 PM

Search Tags


/mathhelpforum @mathhelpforum