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 }}^{+}$ $=$ ${\displaystyle \bigcup _{n=1}^{\mathrm{\infty }}}{\mathrm{\Sigma }}^n$

${\mathrm{\Sigma }}^{*}$ $=$ ${\displaystyle \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{♣},\mathrm{\wp },63,a,A\}$. The following are all languages over $\mathrm{\Sigma }$:

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

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

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

• $\{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 non-negative integers.

Title	language
Canonical name	Language
Date of creation	2013-03-22 12:17:10
Last modified on	2013-03-22 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