# 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$, $\cdots$ in lexicographic order.

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

 $\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 $A$ (also denoted as $\chi_{A}$) is the concatenation of the values of the characteristic function in the natural order.

Title standard enumeration StandardEnumeration 2013-03-22 13:33:12 2013-03-22 13:33:12 mathcam (2727) mathcam (2727) 21 mathcam (2727) Definition msc 68Q45 msc 03B65 lexicographic enumeration characteristic function characteristic sequence