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?

  • $\begingroup$ Isn't it trivial? Or are you looking for a very strict mathematical proof like this? $\endgroup$ – xskxzr Sep 11 '19 at 16:47
  • $\begingroup$ I'm looking for a strict mathematical proof for this problem. $\endgroup$ – Mikael Törnwall Sep 11 '19 at 16:48
  • $\begingroup$ This is only true for languages over finite alphabets. $\endgroup$ – Saswat Padhi Sep 11 '19 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.


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.