1rbraceStandardEnumerationOfLbrace0 2003-04-05 17:43:12 2006-09-17 08:17:17 Definition characteristic function characteristic sequence standard enumeration language characteristic function characteristic sequence \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \PMlinkescapeword{natural} \PMlinkescapeword{order} The \emph{standard enumeration} of $\lbrace 0,1\rbrace ^{*}$ 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 \emph{characteristic function} of a language $A$ is $\chi_{A}:\mathbb{N}\rightarrow \lbrace 0, 1\rbrace$ such that \[\chi_{A}(n)=\begin{cases} 1,\text{ if }s_n \in A\\ 0,\text{ if }s_n \notin A. \end{cases}\] The \emph{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.