Results 1 to 9 of 9

Math Help - Inductive definition of string concatenation?

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Inductive definition of string concatenation?

    I am trying to formulate an inductive definition of string concatenation and am having a little trouble. What I've gotten so far is something like this:

    (Basis) if y = empty string, then xy = x
    (Step) We know a string can be build by adding one symbol at a time to the empty string, so string concatenation can take place if y = ab where a is a string and b is a single symbol (xa)b = xy

    I'm having trouble with the concept, so if anyone could help me clean this up and gain a better understanding, it would really help. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Inductive definition of string concatenation?

    Quote Originally Posted by KevinMulito View Post
    I am trying to formulate an inductive definition of string concatenation and am having a little trouble. What I've gotten so far is something like this:

    (Basis) if y = empty string, then xy = x
    (Step) We know a string can be build by adding one symbol at a time to the empty string, so string concatenation can take place if y = ab where a is a string and b is a single symbol (xa)b = xy

    I'm having trouble with the concept, so if anyone could help me clean this up and gain a better understanding, it would really help. Thank you.
    What context is this? Are you doing free groups and having trouble understanding inductively how things work?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Re: Inductive definition of string concatenation?

    Yes, it's just very general. It's a bit fuzzy for me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Inductive definition of string concatenation?

    Quote Originally Posted by KevinMulito View Post
    Yes, it's just very general. It's a bit fuzzy for me.
    So, it's free groups? You're having trouble understanding concatenation? I mean, you just put two words together to create a bigger word. What in particular are you having trouble with?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Re: Inductive definition of string concatenation?

    I'm having trouble understanding how to properly construct an inductive definition. Mine seems overly wordy and complex.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,515
    Thanks
    769

    Re: Inductive definition of string concatenation?

    Before you can give a recursive definition of concatenation, you need an inductive definition of strings (inductive types and recursive functions go hand-in-hand).

    So,

    (1) the empty string is a string;
    (2) if x is a string and a is a symbol, then xa is a string;
    (3) all strings are built using rules (1) and (2)

    (Basis) if y = empty string, then xy = x
    (Step) We know a string can be build by adding one symbol at a time to the empty string, so string concatenation can take place if y = ab where a is a string and b is a single symbol (xa)b = xy
    This is basically correct. Given two strings x and y, the program analyzes y. If it is the empty string, the program returns x. If y = y'b, then y' is simpler than y and so the program should already know how to compute xy'. After doing that, it adds b to xy' using rule (2) and returns the result.

    Instead of (xa)b = xy in the quote above I would write xy = (xa)b because the left-hand side is what has to be computed and the right-hand side is how to compute it.

    Usually strings are defined so that new symbols are added on the left.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Inductive definition of string concatenation?

    One common notion of a string is that a string is a finite sequence (a finite sequence is a function whose domain is a natural number).

    For the empty string 0, let length(0) = 0
    For a non-empty string f, let length(f) = max(dom(f))+1.

    Then the concatenation of two strings f and g may be defined ['u' for binary union and 'E' for the existential quantifier]:

    concat(f g) = f u {<x y> | En(<n y> in g & x = n+length(f)}

    That definition is not couched inductively.

    Then among key theorems is that the concatenation operation is associative.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Inductive definition of string concatenation?

    Quote Originally Posted by emakarov View Post
    Before you can give a recursive definition of concatenation, you need an inductive definition of strings (inductive types and recursive functions go hand-in-hand).

    So,

    (1) the empty string is a string;
    (2) if x is a string and a is a symbol, then xa is a string;
    But what is
    xa
    ?

    That is, what does the notation of 'x' followed by 'a' stand for? I would think it stands for some kind of concatenation. But you were definining 'string' in order to then define 'concatenation', so there can't be an appeal to concatenation in the definition of 'string' without circularity.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,515
    Thanks
    769

    Re: Inductive definition of string concatenation?

    That is, what does the notation of 'x' followed by 'a' stand for? I would think it stands for some kind of concatenation. But you were definining 'string' in order to then define 'concatenation', so there can't be an appeal to concatenation in the definition of 'string' without circularity.
    The OP should clarify the context (functional programming, free groups, etc.). He repeatedly refused to do this in response to Drexel's question.

    Recursive definitions are often used in functional programming, where they go together with inductive types. When defining a new type, we introduce new functional symbols, called constructors, of given types, and say that all terms of the newly defined inductive type are built from those constructors. E.g., when defining the type of natural numbers Nat, we introduce two constructors: 0 : Nat and s : Nat -> Nat. Similarly, when we are defining the type of strings String T for some other type T, we introduce two constructors: nil : String T and cons : String T -> T -> String T. So, after the type is defined, we already have functions to build strings one symbol at a time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Concatenation Sequences
    Posted in the Math Forum
    Replies: 0
    Last Post: July 3rd 2010, 08:42 AM
  2. Replies: 2
    Last Post: January 29th 2010, 05:48 AM
  3. String
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 23rd 2009, 05:04 PM
  4. inductive definition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 11th 2009, 10:05 AM
  5. inductive
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2008, 12:08 PM

Search Tags


/mathhelpforum @mathhelpforum