language
Let $\mathrm{\Sigma}$ be an alphabet. We then define the following using the powers of an alphabet and infinite^{} union, where $n\in \mathbb{Z}$.
${\mathrm{\Sigma}}^{+}$  $=$  $\bigcup _{n=1}^{\mathrm{\infty}}}{\mathrm{\Sigma}}^{n$  
${\mathrm{\Sigma}}^{*}$  $=$  $\bigcup _{n=0}^{\mathrm{\infty}}}{\mathrm{\Sigma}}^{n}={\mathrm{\Sigma}}^{+}\cup \{\lambda \$ 
where $\lambda $ is the element called empty string. A string is an element of ${\mathrm{\Sigma}}^{*}$, meaning that it is a grouping of symbols from $\mathrm{\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. ${\mathrm{\Sigma}}^{+}$, like ${\mathrm{\Sigma}}^{*}$, contains all finite strings except that ${\mathrm{\Sigma}}^{+}$ does not contain the empty string $\lambda $. Given a string $s\in {\mathrm{\Sigma}}^{*}$, a string $t$ is a substring of $s$ if $s=utv$ for some strings $u,v\in {\mathrm{\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 $\mathrm{\Sigma}$ is a subset of ${\mathrm{\Sigma}}^{*}$, meaning that it is a set (http://planetmath.org/Set) of strings made from the symbols in the alphabet $\mathrm{\Sigma}$.
Take for example an alphabet $\mathrm{\Sigma}=\{\mathrm{\u2663},\mathrm{\wp},63,a,A\}$. The following are all languages over $\mathrm{\Sigma}$:

•
$\{aaa,\lambda ,A\mathrm{\wp}63,63\mathrm{\u2663},AaAaA\}$,

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

•
$\{63\}$

•
$\{{a}^{2n}\mid n\ge 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 $\mathrm{\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 $\mathrm{\Sigma}$, the alphabet of $L$ is defined as the maximal subset $\mathrm{\Sigma}(L)$ of $\mathrm{\Sigma}$ such that every symbol in $\mathrm{\Sigma}(L)$ occurs in some word in $L$. Equivalently, define the alphabet of a word $w$ to be the set $\mathrm{\Sigma}(w)$ of all symbols that occur in $w$, then $\mathrm{\Sigma}(L)$ is the union of all $\mathrm{\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 $$. Then the length of a string $f:X\to A$ is just $\mathrm{dom}(f)$. This specializes to the finite case if we take $X$ to be the set of all nonnegative integers.
Title  language 
Canonical name  Language 
Date of creation  20130322 12:17:10 
Last modified on  20130322 12:17:10 
Owner  mps (409) 
Last modified by  mps (409) 
Numerical id  28 
Author  mps (409) 
Entry type  Definition 
Classification  msc 03C07 
Classification  msc 68Q45 
Synonym  $\lambda $free 
Related topic  Alphabet 
Related topic  ContextFreeLanguage 
Related topic  RegularLanguage 
Related topic  DeterministicFiniteAutomaton 
Related topic  NonDeterministicFiniteAutomaton 
Related topic  KleeneStar 
Related topic  FormalGrammar 
Related topic  FirstOrderLanguage 
Related topic  TermsAndFormulas 
Related topic  Word 
Defines  string 
Defines  empty language 
Defines  substring 
Defines  proper language 
Defines  improper language 
Defines  alphabet of a language 
Defines  alphabet of a word 
Defines  finite language 
Defines  atomic language 