Search code examples
programming-languagesdiscrete-mathematicsformal-languagesautomaton

Finite strings but possibly infinite language


We know that a string is finite but on the other hand we know that a language is a set of strings(possibly infinite) over an alphabet. Isn't this relation a contradiction?


Solution

  • Every natural number has a finite number of digits in it. Yet, there's an infinite number of natural numbers.

    In other words, as long as there's no bound on the number of digits per number, you can always create longer and longer numbers from the same alphabet.