String (computer Science) - Formal Theory

Formal Theory

See also: Tuple

Let Σ be an alphabet, a non-empty finite set. Elements of Σ are called symbols or characters. A string (or word) over Σ is any finite sequence of characters from Σ. For example, if Σ = {0, 1}, then 0101 is a string over Σ.

The length of a string is the number of characters in the string (the length of the sequence) and can be any non-negative integer. The empty string is the unique string over Σ of length 0, and is denoted ε or λ.

The set of all strings over Σ of length n is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. Note that Σ0 = {ε} for any alphabet Σ.

The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn,

For example, if Σ = {0, 1}, Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Although Σ* itself is countably infinite, all elements of Σ* have finite length.

A set of strings over Σ (i.e. any subset of Σ*) is called a formal language over Σ. For example, if Σ = {0, 1}, the set of strings with an even number of zeros ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}) is a formal language over Σ.

Read more about this topic:  String (computer Science)

Famous quotes containing the words formal and/or theory:

    Good gentlemen, look fresh and merrily.
    Let not our looks put on our purposes,
    But bear it as our Roman actors do,
    With untired spirits and formal constancy.
    William Shakespeare (1564–1616)

    ... the first reason for psychology’s failure to understand what people are and how they act, is that clinicians and psychiatrists, who are generally the theoreticians on these matters, have essentially made up myths without any evidence to support them; the second reason for psychology’s failure is that personality theory has looked for inner traits when it should have been looking for social context.
    Naomi Weisstein (b. 1939)