1
$\begingroup$

Let $L$ be an infinite language.
Is it true to say that for all $k∈\Bbb N$, we can find $w∈L$ so that $|w|>k$?

I think it's part of an infinite language definition, but I didn't find it formally anywhere, so I also tried to prove it:
Let $k∈N$. Proof by contradiction: we will assume that we don't have $w∈L$ so that $|w|>k$. so the maximum length of a word in $L$ can be $p$ ($p$ is at most $k$).
We know that $Σ^p$ is a finite language, and therefore $Σ^m$ is finite for all $m<p$.
So we get that $Σ^0∪Σ^1∪\dots∪Σ^p$ is a finite language, and we also know that $|L|≤|Σ^0+Σ^1+\dots+Σ^p|$. so we got that L is finite- contradiction.

$\endgroup$

1 Answer 1

1
$\begingroup$

The theorem is true iff $\Sigma$ is finite, and your proof works correctly in this case. If $\Sigma$ is infinite, then the set $\{w\in\Sigma^*\mid|w|=1\}$, which is equinumerous to $\Sigma$, is an infinite language with no words of length $>1$.

It is, however, not correct to say that it is true by definition. The definition of "$L$ is an infinite language" is that $L$ contains infinitely many distinct words, or equivalently (if that sounds like restating the definition) for any finite sequence $S$ of words there is a word in $L\setminus S$.

$\endgroup$
2
  • $\begingroup$ Tnx. I indid meant that Σ is finite, just forgot to mention that. $\endgroup$
    – Rodrigo
    Commented Nov 30, 2015 at 16:54
  • $\begingroup$ @Rodrigo Also, $p$ is not needed in your proof, you can just take $p=k$. $\endgroup$ Commented Nov 30, 2015 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .