1 - Basic Notions about Strings

---

Definitions

• An alphabet is a finite set of elements, which could be strings, words or phrases: . The cardinality of an alphabet is the number of elements in it: .
• A string is an ordered set of atomic elements (possibly repeated) from an alphabet; so, given an alphabet , the strings are all possible combination of symbols of the alphabet .
• A language is a finite or infinite set of strings generated using a given alphabet; so, given an alphabet , , are languages. We define a language as an unordered set non-atomic elements (strings) that are in turn sequences of atomic elements (characters or terminals).

The cardinality of a language is the number of elements in it; for example, the cardinality of is given by . A special case of a language is the empty language, denoted by the empty set (), which has no elements (so ). It’s possible to define the cardinality of a particular element (string) of a language, for example the cardinality of in is .

A language could be finite or infinite, depending on the number of elements it contains. If the language has a finite number of elements, it’s called a dictionary. If the alphabet contains only one element () and the language is defined as , it’s called a Omega language¹.

Definition

The length of a string is the number of atomic elements of it and it’s always a non-negative integer: .

The length of a string is denoted by , so , .

Properties

Two strings and are equal if and only if:

1. They have the same length: .
2. They have the same elements in the same order.

So, given the strings and , we have that

Operations on Strings

Concatenation

Concatenation is a fundamental operation that combines two or more strings to form a new string. When we refer to the concatenation of two strings and , we are essentially joining them end-to-end. For instance, if we have two strings defined as:

• (where are individual characters of string )
• (where are individual characters of string )

the concatenation of strings and is denoted as and can be mathematically expressed as:

This notation reflects that the characters of string follow immediately after the characters of string in the newly formed string .

Properties of Concatenation

1. Associativity: Concatenation is an associative operation. This means that the order in which strings are concatenated does not affect the final result. For strings , , and , the following holds true:

In both cases, the strings are concatenated in such a way that the final string remains the same, regardless of how they are grouped.

2. Length of Concatenation: The length of the concatenated string is equal to the sum of the lengths of the original strings and . If represents the length of string and represents the length of string , then:

This property is essential in analyzing the complexity of string operations and understanding memory allocation in programming.

Definition

The empty string (also known as the null string) is a unique string that contains no characters, denoted by .

The empty string acts as the neutral element for the concatenation operation, meaning that concatenating any string with the empty string does not alter :

This property is crucial in various string manipulation algorithms and forms the basis for many theoretical concepts in formal languages.

Important

The empty string is a valid string of length zero, whereas the empty set represents a collection with no elements at all. This distinction can have significant implications in theoretical computer science and programming, especially in discussions involving automata, languages, and data structures.

Substring

Definition

A substring of a string is a sequence of characters derived from by removing zero or more characters from both the beginning and the end. For instance, consider a string defined as , where:

• represents the prefix of . A prefix is any substring that includes the starting characters of , extending up to (but not including) any characters that follow .
• signifies the suffix of . A suffix is any substring that comprises the ending characters of , starting from some position in and extending to the end of the string.
• is identified as the substring (or infix) of . A substring is any sequence of characters that appears within , excluding the entire string itself.

A proper substring is defined as when both and are not empty (). This means that a proper substring cannot be identical to the original string, thus ensuring that is shorter than .

Additionally, the notation is used to denote the first characters of the string . It is expressed mathematically as follows:

where represents each character in the string. This notation is useful for identifying (or extracting) the initial segment of a string, which can be essential for various string manipulation algorithms and operations.

Example

Let’s consider the string :

• Prefix: “comp” (could also be “c”, “co”, “com”, etc.)
• Suffix: “uter” (could also be “r”, “er”, “ter”, etc.)
• Substring: “put” (this is an example of an infix)
• Proper Substring: “comp” is a proper substring of “computer” since it does not equal the entire string.

Mirroring (or Reflection)

Definition

Mirroring (also known as reflection) of a string is an operation that creates a new string by reversing the order of the characters in . For a string composed of elements , the mirroring operation is defined as:

Example

Consider two strings and .

• The concatenation of these strings can be expressed as .
• The mirroring of the concatenated string results in: .

Key Properties of the Mirroring Operation:

1. Involution Property: The mirroring of the mirrored string yields the original string, represented as:

2. Reversal of Concatenation: The mirroring of the concatenation of two strings results in the concatenation of the mirrored strings taken in reverse order:

3. Empty String: The mirroring of the empty string is the empty string itself:

Repetition (or Iteration)

Repetition (or iteration) of a string refers to the process of creating a new string by repeating a specified number of times, where is a non-negative integer. The notation indicates the repetition of , defined as follows:

• (the empty string)
• (the string itself)
• (the string repeated twice)

For example, if , then: .

The repetition of the empty string is always the empty string, regardless of the value of :

For instance, if we take (which represents the string ""), the repetition of would be: .

Precedence of Operations

• The mirroring operation takes precedence over the concatenation operation. For example, for the string :

  here, mirroring does not change the order of characters. However, if we mirror the entire concatenated string, we have:

• The power operation (repetition) also has precedence over concatenation. For instance:

  While for the concatenated string, we find:

Operations on Languages

In formal language theory, operations on languages are fundamental concepts used to manipulate and combine languages in various ways. Each operation applies to the strings in the language, and is defined in a way that can handle any string in the language.

Prefix of a Language

A prefix of a language refers to all initial segments of strings in the language.

Definition

Formally, the prefix of a language is a new language that contains all strings such that is a prefix of some string in . This is expressed as:

where, and are non-empty strings (), and is derived from concatenating and .

A language is prefix-free if no string in the language is a prefix of another string in the same language.

Example

• Consider the language . This language is prefix-free because no string of the form can be a prefix of another string of the same form.
• For the language , is a prefix of , so it is not prefix-free.

is prefix (or suffix, or substring) of any string in any language, including itself.

Concatenation of Languages

Concatenation combines two languages by concatenating strings from each language. For languages and , the concatenation is defined as:

Example

Given two languages and , the concatenation of and is:

This results in strings such as .

Power of a Language

The power operation on a language is defined as repeated concatenation of the language with itself. For a non-negative integer , the ^th power of is given by:

For example, is the set containing only the empty string given by the power of of any language.

Example

For the language , the second power of is:

Since the sum of any two even numbers is still even, the language remains unchanged.

WARNING

This means that the empty set is not the same as the set containing the empty string.

Warning

Given and , for the language , the set is a subset of .

The power operator allows us to expressively define the language of the strings that have a length not greater than (less than or equal to) a given fixed integer . For example, given and a language , the language is .

Notice the role of , which allows us to obtain all the strings of length 0, 1, 2. In order to exclude the empty string, we can do as follow: .

Set-Theoretic Operations

Languages can also be combined using set-theoretic operations:

• Union (): Combines all elements from two languages.
• Intersection (): Consists of elements common to both languages.
• Complement ( or ): Consists of all strings over an alphabet that do not belong to the language.

Definition

The universal language over an alphabet contains all possible strings, including the empty string. It can be written as:

Given a language over the alphabet , the complement of is defined as the set-theoretic difference with respect to the universal language over . Equivalently, it’s the set of all the strings over the alphabet that do not belong to

where represents all possible strings over . The complement of a finite language is always an infinite language, while the complement of an infinite language could be finite or infinite.

Example

Given an alphabet and two languages and (examples are and ), we have:

while

In both natural and artificial languages, the phrase can be of any length, but only formulas of finite length can be written to define a language. It’s necessary to introduce some operators to create infinitely many strings.

Star Operator (Kleene Star)

The star operator (also known as the Kleene star or concatenation closure) allows the generation of an infinite set of strings by concatenating elements of a language. The result is the union of all powers of the language, including the case where the language is raised to the power of zero (which is always the empty string, denoted by ).

Definition

The concatenation closure is defined as:

This means that the star operator applied to a language produces a new language that contains the empty string, all the strings from , as well as all possible concatenations of strings from .

Example

Consider a finite language . The star operator applied to results in: This language is infinite because it includes all possible concatenations of strings from , including the empty string.

For languages where the elements are of a regular pattern, the star operator can sometimes yield results identical to the base language. For instance:

Properties of the Star Operator:

1. Monotonicity: . Every string in is also in .
2. Concatenation Closure: If and , then .
3. Idempotence: Applying the star operator multiple times does not alter the result: .
4. Mirror Operation: The star operator commutes with the mirror operation (reversing strings): .
5. Special Cases:

• The star of the empty set is the set containing only the empty string: .
• The star of the set containing the empty string is itself: .

Example of an identifier, modeled as a string of letters and digits (alphanumeric characters), of arbitrary length (not null), but starting with a letter (not with a digit).

• The alphabet set is .
• The digit set is .

The alphabet to be used is the union of the two sets: . The identifier is defined as the set of all strings that start with a letter and are followed by any number of letters and digits: . The star operator is used to define the set of all strings that start with a letter and are followed by any number of letters and digits.

For example, setting an identifier of characters, the language is defined as

---

The C language would admit the underscore _ as a character in the identifier, but not as the initial symbol. The identifier in C is defined as the set of all strings that start with a letter and are followed by any number of letters, digits, and underscores:

Cross Operator (Kleene Cross)

The cross operator (or Kleene cross, denoted by ) is similar to the star operator, but it excludes the empty string. It is the non-reflexive closure of the language, meaning it only includes strings formed by at least one occurrence of elements from .

Definition

The cross operator is defined as:

the union of all powers of starting from (and so excluding the empty string ).

Example

For a language , the cross operator results in:

Quotient Operator

The quotient operator shortens the strings of a language by removing suffixes that belong to another language. It can be defined as:

This operation removes the suffixes in from the strings in .

Example

Given two languages and the quotient of by is:

However, the quotient of by is empty:

Footnotes

1. this has not a real application, but it’s useful for theoretical purposes ↩