1
$\begingroup$

Is there a name for this infinite language?

$$L = \{ 0(,1)^*(,2)^*(,3)^*....(,n)^* \;\mid n \geq 1\}$$

A string $w \in L$ is simply an ordered list of increasing integers in which every integer $\geq 1$ can be repeated 0 or more times, for example "0", "0,1", "0,1,2,2", "0,1,2,3", "0,1,1,4,4,4,21,21".

Or perhaps a name for its unary variant: $L_U = \{ 1^{x_1}(,1^{x_1})^*,1^{x_2}(,1^{x_2})^*,...,1^{x_n}(,1^{x_n})^* \mid x_1<x_2<...<x_n\}$

$\endgroup$
6
$\begingroup$

Non-decreasing sequences of natural numbers.

$\endgroup$
  • 2
    $\begingroup$ I completely missed the question I had in mind :-D ... however I think that your answer is good for the mega-trivial question above :-) ... $\endgroup$ – Vor Oct 24 '13 at 19:44
1
$\begingroup$

I don't know of any standard name, but I think calling it the language of sorted lists (or: sorted lists of integers) would be reasonable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.