Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Induction and Grammar

  1. #1
    Junior Member
    Joined
    Aug 2013
    From
    hcm
    Posts
    27

    Induction and Grammar

    Hi all, I have some problems that I'm not sure about their solution.

    Let B be the set of all bit-string (non-null strings over the alphabet {0,1})
    a/ Define the set B inductively
    b/ Find an unambiguous grammar for the non-negative binary integers such that every number is represented uniquely without extra 0's at the beginning (ex: 1011011001)

    My solution is
    a/ Basic step: 0 ∈ B, 1 ∈ B
    I don't know how to do the recursive step.

    b/ S->1 | 1A
    A->0| 0A | S
    I'm not sure if I'm right. Do we have another way to solve it?

    Please, help me to check them. Thank for your helping.

    Last edited by math88; March 28th 2014 at 05:09 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Induction and Grammar

    Quote Originally Posted by math88 View Post
    a/ Basic step: 0 ∈ B, 1 ∈ B
    I don't know how to do the recursive step.
    You don't know how to convert a binary string of length n into a binary string of length n + 1?

    Quote Originally Posted by math88 View Post
    b/ S->1 | 1A
    A->0| 0A | S
    I believe this is a correct grammar that produces all positive numbers. It is unambiguous because each intermediate string contains a single nonterminal.

    I would use part (a) here. A nonnegative binary number is either a 0 or a 1 followed by a possibly empty binary string. So the following grammar should work.

    S -> 0 | 1A
    A -> 1A | 0A | empty
    Thanks from math88
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2013
    From
    hcm
    Posts
    27

    Re: Induction and Grammar

    Quote Originally Posted by emakarov View Post
    You don't know how to convert a binary string of length n into a binary string of length n + 1?
    So part a) is 0 ∈ B, 1 ∈ B and if x,y ∈ B => xy ∈ B
    Am I right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Induction and Grammar

    Quote Originally Posted by math88 View Post
    So part a) is 0 ∈ B, 1 ∈ B and if x,y ∈ B => xy ∈ B
    This works, but a more obvious answer is

    0 ∈ B, 1 ∈ B and if x ∈ B => 0x ∈ B and 1x ∈ B.

    Your answer requires a moment of thought to understand why it generates all strings, though it is obvious.
    Thanks from math88
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 12:51 PM
  2. Simplification grammar
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: June 30th 2010, 06:16 AM
  3. Grammar problem
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 29th 2010, 06:42 AM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 09:58 AM
  5. Phrase-structure grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 11:01 AM

Search Tags


/mathhelpforum @mathhelpforum