Finite strings but possibly infinite language

760 Views Asked by At

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?

2

There are 2 best solutions below

6
On BEST ANSWER

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.

0
On

In the phrase "a language is a set of strings(possibly infinite) over an alphabet", the parenthetical observation relates to the set, not to the strings. That is, it might equally well have been described as "a set (possibly infinite) of (finite) strings". There is no contradiction in the definition (properly understood), because it is the strings which are said to be finite and the set which is said to be infinite.

Note, by the way, that it is possible to allow infinite strings and to consider the properties of languages defined as sets of finite or infinite strings, but pretty much all work on formal languages restricts sentences to finite length; the restriction makes a lot of questions tractable which are not tractable for the case where infinite strings are allowed.