PlanetMath: standard enumeration

(more info)

Math for the people, by the people.

Main Menu

standard enumeration

(Definition)

The standard enumeration of $\lbrace 0,1\rbrace ^{*}$ is the sequence of strings $s_0 =\lambda$ , , , , , $\cdots$ in lexicographic order.

The characteristic function of a language is $\chi_{A}:\mathbb{N}\rightarrow \lbrace 0, 1\rbrace$ such that

$\displaystyle \chi_{A}(n)=\begin{cases} 1,\text{ if }s_n \in A\ 0,\text{ if }s_n \notin A. \end{cases}$

The characteristic sequence of a language

(also denoted as $\chi_A$ ) is the concatenation of the values of the characteristic function in the natural order.

"standard enumeration" is owned by mathcam. [ full author list (3) | owner history (1) ]

(view preamble)

Other names:

lexicographic enumeration

Also defines:

characteristic function, characteristic sequence

Keywords:

standard enumeration, language, characteristic function, characteristic sequence

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

Cross-references: concatenation, language, lexicographic order, strings, sequence
There are 6 references to this entry.

This is version 18 of standard enumeration, born on 2003-04-05, modified 2006-09-17.
Object id is 4158, canonical name is 1rbraceStandardEnumerationOfLbrace0.
Accessed 7817 times total.

Classification:

AMS MSC:	03B65 (Mathematical logic and foundations :: General logic :: Logic of natural languages)
	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact