Discrete Structures

A Recursive Definition of Strings

Last Update: 30 March 2009

Note: NEW or UPDATED material is highlighted

  1. Many objects (such as sets and "strings") can be defined recursively:

    Compare building blocks (e.g., Legos):

    * The recursive case tells you how to make more of something if you already have some.
    * The base case tells you how to get some in the first place.
      (In fact, it gives it to you for free.)

  2. In what follows, we will see how to recursively define "strings": sequences of symbols that can be used to model languages, mathematical codes, etc.

  3. Definition:

    An atomic symbol isdef a (single) mark on paper (or multiple marks that are considered to be a single object).

  4. Definition:

    Concatenation isdef an abstract operation on symbols that:

    1. Remark:

      Concatenation is usually implemented (on paper) by the physical act of "juxtaposition",
      i.e., writing down a symbol and then writing down a(nother) symbol immediately to the right of the first one, with no blank spaces in between.

    2. Remark:

      If the blank (" ", or "_" in order to make it visible) is an atomic symbol,
      then two atomic symbols with a blank in between them is a molecular symbol consisting of 3 atomic symbols, one of which is the blank.

  5. Definition:

    The empty symbol is an atomic symbol.

  6. Remark:

    Let Σ be a finite set of symbols.

    1. This has nothing to do with summations!

    2. λ ∈ Σ

  7. Recursive Definition of "string":

  8. Remark:

    If we interpret the symbols as words (instead of letters)—possibly including the blank, and possibly including these symbols:

    —then strings are sentences consisting of those words, possibly separated by spaces and possibly with punctuation.

    We could also have a "grammar" that tells us which sentences are grammatically correct (like "this sentence is grammatically correct")
    and which ones aren't (like "this sentence grammatically incorrect").

  9. Remark:

    If we interpret the symbols as sentences, then strings are paragraphs consisting of those sentences.

    This is how we can mathematically (and computationally!) model languages.

Copyright © 2009 by William J. Rapaport (rapaport@cse.buffalo.edu)