You are here
Homelanguage
Primary tabs
language
Let $\Sigma$ be an alphabet. We then define the following using the powers of an alphabet and infinite union, where $n\in\mathbb{Z}$.
$\displaystyle\Sigma^{+}$  $\displaystyle=$  $\displaystyle\bigcup_{{n=1}}^{{\infty}}\Sigma^{n}$  
$\displaystyle\Sigma^{*}$  $\displaystyle=$  $\displaystyle\bigcup_{{n=0}}^{{\infty}}\Sigma^{n}=\Sigma^{+}\cup\{\lambda\}$ 
where $\lambda$ is the element called empty string. A string is an element of $\Sigma^{*}$, meaning that it is a grouping of symbols from $\Sigma$ one after another (via concatenation). For example, $abbc$ is a string, and $cbba$ is a different string. A string is also commonly called a word. $\Sigma^{+}$, like $\Sigma^{*}$, contains all finite strings except that $\Sigma^{+}$ does not contain the empty string $\lambda$. Given a string $s\in\Sigma^{*}$, a string $t$ is a substring of $s$ if $s=utv$ for some strings $u,v\in\Sigma^{*}$. For example, $lp,al,ha,alpha$, and $\lambda$ (the empty string) are all substrings of the string $alpha$.
Definition. A language over an alphabet $\Sigma$ is a subset of $\Sigma^{*}$, meaning that it is a set of strings made from the symbols in the alphabet $\Sigma$.
Take for example an alphabet $\Sigma=\{\clubsuit,\wp,63,a,A\}$. The following are all languages over $\Sigma$:

$\{aaa,\lambda,A\wp 63,63\clubsuit,AaAaA\}$,

$\{\wp a,\wp aa,\wp aaa,\wp aaaa,\cdots\}$,

The empty set $\varnothing$. In the context of languages, $\varnothing$ is called the empty language.

$\{63\}$

$\{a^{{2n}}\mid n\geq 0\}$
A language $L$ is said to be proper if the empty string does not belong to it: $\lambda\notin L$. A proper language is also said to be $\lambda$free. Otherwise, it is improper. In the examples above, all but the first and the last examples are $\lambda$free. $L$ is a finite language if $L$ is a finite set, and atomic if it is a singleton subset of $\Sigma$, such as the fourth example above. A language can be arbitrarily formed, or constructed via some set of rules called a formal grammar.
Given a language $L$ over $\Sigma$, the alphabet of $L$ is defined as the maximal subset $\Sigma(L)$ of $\Sigma$ such that every symbol in $\Sigma(L)$ occurs in some word in $L$. Equivalently, define the alphabet of a word $w$ to be the set $\Sigma(w)$ of all symbols that occur in $w$, then $\Sigma(L)$ is the union of all $\Sigma(w)$, where $w$ ranges over $L$.
Remark. A language can also be described in terms of “infinite” alphabets. For example, in model theory, a language is built from a set of symbols, together with a set of variables. These sets are often infinite. Another way of generalizing the notion of a language is to allow the strings to have infinite lengths. The way to do this is to think of a string as a partial function $f$ from some set $X$ to the alphabet $A$ such that $\operatorname{dom}(f)<X$. Then the length of a string $f:X\to A$ is just $\operatorname{dom}(f)$. This specializes to the finite case if we take $X$ to be the set of all nonnegative integers.
Mathematics Subject Classification
03C07 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections