standard enumeration

The standard enumeration of ${\{0,1\}}^{*}$ is the sequence of strings $s_0=\lambda$, $s_1=0$, $s_2=1$, $s_3=00$, $s_4=01$, $\mathrm{\cdots }$ in lexicographic order.

The characteristic function of a language $A$ is ${\chi }_A:\mathbb{N}\to \{0,1\}$ such that

$${\chi }_A(n)=\{\begin{array}{cc}1,\text{ if }{s}_n\in A\hfill & \\ 0,\text{ if }{s}_n\notin A.\hfill & \end{array}$$

The characteristic sequence of a language $A$ (also denoted as ${\chi }_A$) is the concatenation of the values of the characteristic function in the natural order.

Title	standard enumeration
Canonical name	StandardEnumeration
Date of creation	2013-03-22 13:33:12
Last modified on	2013-03-22 13:33:12
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	21
Author	mathcam (2727)
Entry type	Definition
Classification	msc 68Q45
Classification	msc 03B65
Synonym	lexicographic enumeration
Defines	characteristic function
Defines	characteristic sequence