Changes

Usually, one compares different formal languages over a fixed resource, but since resources are finite it is no trouble to unite a finite number of them into a common resource.  Without loss of generality, then, one typically has a fixed set <math>\underline{\underline{X}}</math> in mind throughout a given discussion and has to consider a variety of different formal languages that can be generated from the symbols of <math>\underline{\underline{X}}.</math>  These sorts of considerations are aided by defining a number of formal operations on the resources <math>\underline{\underline{X}}</math> and the languages <math>\underline{X}.</math>

Usually, one compares different formal languages over a fixed resource, but since resources are finite it is no trouble to unite a finite number of them into a common resource.  Without loss of generality, then, one typically has a fixed set <math>\underline{\underline{X}}</math> in mind throughout a given discussion and has to consider a variety of different formal languages that can be generated from the symbols of <math>\underline{\underline{X}}.</math>  These sorts of considerations are aided by defining a number of formal operations on the resources <math>\underline{\underline{X}}</math> and the languages <math>\underline{X}.</math>

The '''<math>k^\text{th}\!</math> power of <math>\underline{\underline{X}},</math>''' written as <math>\underline{\underline{X}}^k,</math> is defined as the set of all sequences of length <math>k\!</math> over <math>\underline{\underline{X}}.</math>

The '''<math>k^\text{th}\!</math> power''' of <math>\underline{\underline{X}},</math> written as <math>\underline{\underline{X}}^k,</math> is defined as the set of all sequences of length <math>k\!</math> over <math>\underline{\underline{X}}.</math>

{| align="center" cellspacing="8" width="90%"

{| align="center" cellspacing="8" width="90%"

It is probably worth remarking at this point that all empty sequences are indistinguishable (in a one-level formal language, that is), and thus all sets that consist of a single empty sequence are identical.  Consequently, <math>\underline{\underline{X}}^0 = \{ () \} = \underline{\varepsilon} = \underline{\underline{Y}}^0,</math> for all resources <math>\underline{\underline{X}}</math> and <math>\underline{\underline{Y}}.</math>  However, the empty language <math>\varnothing = \{ \}</math> and the language that consists of a single empty sequence <math>\underline\varepsilon = \{ \varepsilon \} = \{ () \}</math> need to be distinguished from each other.

It is probably worth remarking at this point that all empty sequences are indistinguishable (in a one-level formal language, that is), and thus all sets that consist of a single empty sequence are identical.  Consequently, <math>\underline{\underline{X}}^0 = \{ () \} = \underline{\varepsilon} = \underline{\underline{Y}}^0,</math> for all resources <math>\underline{\underline{X}}</math> and <math>\underline{\underline{Y}}.</math>  However, the empty language <math>\varnothing = \{ \}</math> and the language that consists of a single empty sequence <math>\underline\varepsilon = \{ \varepsilon \} = \{ () \}</math> need to be distinguished from each other.

The '''surplus''' of <math>\underline{\underline{X}},</math> written as <math>\underline{\underline{X}}^+,</math> is defined as the set of all positive length sequences over <math>\underline{\underline{X}}.</math>

The "surplus" of X, written as X+, is defined to be the set of all positive length sequences over X.

X+   =   Ui=1 Xk  =   X1 U ... U Xk U ...

| <math>\underline{\underline{X}}^+ ~=~ \bigcup_{j = 1}^\infty \underline{\underline{X}}^j ~=~ \underline{\underline{X}}^1 \cup \ldots \cup \underline{\underline{X}}^k \cup \ldots</math>

The "kleene star" of X, written as X*, is defined to be the set of all finite sequences over X.

The "kleene star" of X, written as X*, is defined to be the set of all finite sequences over X.