# Prove that a language is bounded if and only if it's finite

Let's assume $$L$$ is a language. $$L$$ is bounded if for some natural number $$n \in \mathbb N$$ applies $$|x| ≤ n$$, where $$|x|$$ is a length of a string, with every $$x \in L$$. Let's also assume that $$L$$ lies in a finite set of alphabets $$\Sigma$$.

How to prove that $$L$$ is bounded if and only if it's finite?

• Isn't it trivial? Or are you looking for a very strict mathematical proof like this? – xskxzr Sep 11 at 16:47
• I'm looking for a strict mathematical proof for this problem. – Mikael Törnwall Sep 11 at 16:48
• This is only true for languages over finite alphabets. – Saswat Padhi Sep 11 at 17:19

The claim holds only for languages over finite alphabets.

### Bounded $$L$$$$\implies$$ Finite $$L$$

Let $$\Sigma$$ be the alphabet of $$L$$ and $$L$$ be bounded by some $$n \in \mathbb{N}$$.

The largest possible such $$L$$, call it $$L^\#$$, is $$\bigcup_{\,i=0}^{\,n} \Sigma^i$$ elements. $$L^\#$$ is finite since $$|L^\#| = \sum_{i=0}^{n} |\Sigma|^i$$. Therefore, any $$L \subseteq L^\#$$ must also be finite.

### Finite $$L$$$$\implies$$ Bounded $$L$$

Let $$x^\#$$ denote the longest string in $$L$$. Such a string must always exist since $$L$$ is finite.

Then, $$\forall x \in L \ldotp |x| \leq |x^\#|$$ and thus, $$L$$ is bounded.

A simple counterexample to the infinite alphabet case:

Consider an infinite alphabet $$\Sigma = \{ s_0, s_1, ... \}$$. The language $$L = \Sigma$$ is bounded since $$\forall x \in L \ldotp |x| \leq 1$$, but is infinite.