Math 2.0

Computer science Definition

String

Builds on AlphabetFree monoid

Definition

Let Σ\Sigma be an alphabet. A string, or word, over Σ\Sigma is a finite sequence w=a1a2⋯anw = a_1 a_2 \cdots a_n with n≥0n \ge 0 and each ai∈Σa_i \in \Sigma. Its length is ∣w∣=n\abs{w} = n. The string with n=0n = 0 is the empty string, written ε\varepsilon. The set of all strings over Σ\Sigma is written Σ∗\Sigma^*. The concatenation of u=a1⋯anu = a_1 \cdots a_n and v=b1⋯bmv = b_1 \cdots b_m is uv=a1⋯anb1⋯bmuv = a_1 \cdots a_n b_1 \cdots b_m.

Remarks

Example: over Σ={a,b}\Sigma = \set{a, b}, w=abaw = aba is a string of length 33, and its concatenation with bb is abababab. Non-example: the infinite sequence ababab⋯ababab\cdots is not a string, since a string has finite length; such sequences are infinite words, studied separately. Concatenation is associative, ∣uv∣=∣u∣+∣v∣\abs{uv} = \abs{u} + \abs{v}, and εw=wε=w\varepsilon w = w \varepsilon = w. So Σ∗\Sigma^* with concatenation is the free monoid on Σ\Sigma. For k≥0k \ge 0, Σk\Sigma^k denotes the set of strings of length kk, and Σ+\Sigma^+ the set of nonempty strings.

Reading path

To understand this page from the ground up, read these 23 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionMonoid, concept, no evidence levelMonoidconceptProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionFunction, definition, no evidence levelFunctiondefinitionCodomain, definition, no evidence levelCodomaindefinitionInjective function, definition, no evidence levelInjective functiondefinitionFree monoid, definition, no evidence levelFree monoiddefinitionSurjective function, definition, no evidence levelSurjective functiondefinitionBijective function, definition, no evidence levelBijective functiondefinitionEquinumerous sets, definition, no evidence levelEquinumerous setsdefinitionFinite set, definition, no evidence levelFinite setdefinitionAlphabet, definition, no evidence levelAlphabetdefinitionString, definition, no evidence levelStringdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Monoid concept
  3. Proposition concept
  4. Set definition
  5. Implication definition
  6. Predicate definition
  7. Ordered pair definition
  8. Existential quantifier definition
  9. Universal quantifier definition
  10. Cartesian product definition
  11. Subset definition
  12. Uniqueness quantifier definition
  13. Binary relation definition
  14. Function definition
  15. Codomain definition
  16. Injective function definition
  17. Free monoid definition
  18. Surjective function definition
  19. Bijective function definition
  20. Equinumerous sets definition
  21. Finite set definition
  22. Alphabet definition
  23. String definition

Where this leads

9 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/String_(computer_science)
About this page
TagD9FCP61J44
URIm2://D9FCP61J44
Kinddefinition
WritingW0 stub
MSC68Q45, 68R15
DefinesString
UsesAlphabet, Free monoid
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by