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>

<pre>

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 "kth power" of X, written as Xk, is defined to be the set of all sequences of length k over X.

Xk  =   {<u1, ..., uk> : ui C X, i = 1 to k}.

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

| <math>\underline{\underline{X}}^k ~=~ \{ (u_1, \ldots, u_k) : u_i \in \underline{\underline{X}}, i = 1 ~\text{to}~ k \}.</math>

By convention for the case where k = 0, this gives X0 = {<>}, that is, the singleton set consisting of the empty sequence.  Depending on the setting, the empty sequence is referred to as the "empty word" or the "empty sentence", and is commonly denoted by an epsilon or a lambda.  In this text, I use the symbol "!" (a stricken exclamation point) as a synonym for the empty sequence <>.  In addition, I use the symbol "!" (a stricken exclamation point underscored) as a synonym for {<>}.

By convention for the case where k = 0, this gives X0 = {<>}, that is, the singleton set consisting of the empty sequence.  Depending on the setting, the empty sequence is referred to as the "empty word" or the "empty sentence", and is commonly denoted by an epsilon or a lambda.  In this text, I use the symbol "!" (a stricken exclamation point) as a synonym for the empty sequence <>.  In addition, I use the symbol "!" (a stricken exclamation point underscored) as a synonym for {<>}.