Representing the strings we use in programming in math notation

Question

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?

Answer 1

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 A², is the set of all two character strings. A⁰ is the set of all zero-length strings and is precisely A⁰ = {ε}. (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^* = A⁰ ∪ A¹ ∪ A² ∪ A³ ... . 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 ∈ Aⁿ be a string of n characters. The length of s is |s| = n.