PlanetMath: language

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

language

(Definition)

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,

is a string, and

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

is a substring of

for some strings $u,v\in\Sigma^*$ . For example,

, and $\lambda$ (the empty string) are all substrings of the string

Definition. A language over $\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\wp63, 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.

A language

is said to be proper if the empty string does not belong to it: $\lambda\notin L$ . Otherwise, it is improper. In the examples above, the first language is improper, while the rest are proper. A language can be arbitrarily formed, or constructed via some set of rules called a formal grammar.

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 from some set to the alphabet such that $\vert\operatorname{dom}(f)\vert<\vert X\vert$ . Then the length of a string $f:X\to A$ is just $\vert\operatorname{dom}(f)\vert$ . This specializes to the finite case if we take to be the set of all non-negative integers.

"language" is owned by mps. [ full author list (4) | owner history (2) ]

(view preamble)

Also defines:

string, empty language, substring, proper language, improper language

Log in to rate this entry.
(view current ratings)

Cross-references: integers, length of a string, partial function, lengths, variables, model theory, terms, formal grammar, empty set, subset, finite, contains, concatenation, empty string, union, infinite, alphabet
There are 160 references to this entry.

This is version 23 of language, born on 2002-02-03, modified 2007-11-27.
Object id is 1767, canonical name is Language.
Accessed 17752 times total.

Classification:

AMS MSC:	03C07 (Mathematical logic and foundations :: Model theory :: Basic properties of first-order languages and structures)
	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)

Pending Errata and Addenda

None.[ View all 4 ]

Discussion

forum policy

No messages.

Interact