Editing String
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
==Definitions== | ==Definitions== | ||
− | An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character''' | + | An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. |
The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.) | The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.) | ||
− | |||
− | |||
For ease of conceptualization, we shall usually assign a ''symbol'', a graphical representation, to each character of the alphabet and, considering a string as a sequence of characters, render it as a sequence of symbols. We shall usually do so in '''boldface''', but in this section we shall use ''italics'' to avoid confusion with terms being defined, hence, ''PEG''. On other occasions we may choose to represent them with the ordered list notation, hence, [''P'',''E'',''G'']. (This form is useful when the symbols consist of more than one glyph, as can be the case when they are integers; see below.) We will often number the characters of strings, sometimes starting from zero, sometimes starting from one. | For ease of conceptualization, we shall usually assign a ''symbol'', a graphical representation, to each character of the alphabet and, considering a string as a sequence of characters, render it as a sequence of symbols. We shall usually do so in '''boldface''', but in this section we shall use ''italics'' to avoid confusion with terms being defined, hence, ''PEG''. On other occasions we may choose to represent them with the ordered list notation, hence, [''P'',''E'',''G'']. (This form is useful when the symbols consist of more than one glyph, as can be the case when they are integers; see below.) We will often number the characters of strings, sometimes starting from zero, sometimes starting from one. | ||
Line 25: | Line 23: | ||
Two strings with the same alphabet can be '''concatenated'''. To concatenate two strings is to link them together to give a new string which begins with the first and ends with the second with no overlap. Formally, the concatenation of strings <math>S</math> and <math>T</math> is denoted <math>ST</math> and has the following three properties: | Two strings with the same alphabet can be '''concatenated'''. To concatenate two strings is to link them together to give a new string which begins with the first and ends with the second with no overlap. Formally, the concatenation of strings <math>S</math> and <math>T</math> is denoted <math>ST</math> and has the following three properties: | ||
− | + | # <math>S \sqsubset ST</math> | |
− | + | # <math>T \sqsupset ST</math> | |
− | + | # <math>|ST| = |S|+|T|</math> | |
For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative. | For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |