Search code examples
stringmathnotation

Representing the strings we use in programming in math notation

Now I'm a programmer who's recently discovered how bad he is when it comes to mathematics and decided to focus a bit on it from that point forward, so I apologize if my question insults your intelligence.

In mathematics, is there the concept of strings that is used in programming? i.e. a permutation of characters.

As an example, say I wanted to translate the following into mathematical notation:

let s be a string of n number of characters.

Reason being I would want to use that representation in find other things about string s, such as its length: len(s).

How do you formally represent such a thing in mathematics?

Talking more practically, so to speak, let's say I wanted to mathematically explain such a function:

fitness(s,n) = 1 / |n - len(s)|

Or written in more "programming-friendly" sort of way:

fitness(s,n) = 1 / abs(n - len(s))

I used this function to explain how a fitness function for a given GA works; the question was about finding strings with 5 characters, and I needed the solutions to be sorted in ascending order according to their fitness score, given by the above function.

So my question is, how do you represent the above pseudo-code in mathematical notation?

Solution

  • You can use the notation of language theory, which is used to discuss things like regular languages, context free grammars, compiler theory, etc. A quick overview:

    • A set of characters is known as an alphabet. You could write: "Let A be the ASCII alphabet, a set containing the 128 ASCII characters."

    • A string is a sequence of characters. ε is the empty string.

    • A set of strings is formally known as a language. A common statement is, "Let s ∈ L be a string in language L."

    • Concatenating alphabets produces sets of strings (languages). A represents all 1-character strings, AA, also written A2, is the set of all two character strings. A0 is the set of all zero-length strings and is precisely A0 = {ε}. (It contains exactly one string, the empty string.)

    • A* is special notation and represents the set of all strings over the alphabet A, of any length. That is, A* = A0 ∪ A1 ∪ A2 ∪ A3 ... . You may recognize this notation from regular expressions.

    • For length use absolute value bars. The length of a string s is |s|.

    So for your statement:

    let s be a string of n number of characters.

    You could write:

    Let A be a set of characters and s ∈ An be a string of n characters. The length of s is |s| = n.