|
|
|
Viewing Version
16
of
'standard enumeration'
|
[ view 'standard enumeration'
|
back to history
]
| Title of object: |
standard enumeration |
| Canonical Name: |
1rbraceStandardEnumerationOfLbrace0 |
| Type: |
Definition |
| Created on: |
2003-04-05 17:43:12 |
| Modified on: |
2004-03-07 06:38:14 |
| Classification: |
msc:03-XX, msc:68-XX |
| Keywords: |
standard enumeration, language, characteristic function, characteristic sequence |
| Defines: |
characteristic function, characteristic sequence |
| Synonyms: |
standard enumeration=lexicographic enumeration |
Revision comment (for changes between this and next version):
| Changes for correction #6007 ('reclassify'). |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts} |
Content:
\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 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 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. |
|
|
|
|
|
