Infinite Language vs. finite language

Question

I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.

I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a finite state automaton.

It also doesn't help that the Sipser book doesn't really make this distinction (at least as far as I can tell). A question about infinite/finite languages and their relationship to regular languages came up in a sample exam.

Answer 1

Oh my. This seems like a confusion caused by the (old school) terminology of "finite-state language" as a synonym for what is known today as "regular language".

Anyways, the standard definitions for finite/infinite accepted these days regard only the size of the language:

1. a finite language is any set $L$ of strings, of finite cardinality, $|L|<\infty$.
2. an infinite language is any set $L$ of strings, of infinite ($\aleph_0$) cardinality $|L|=\infty$.

A finite $L$ is always regular.

An infinite $L$ can be regular (sometimes called "finite-state"), decidable (sometimes called "recursive"), non-regular (non-finite-state), non-decidable, etc.,

Answer 2

A language is a set of strings. It is finite if it has a finite number of strings in it.

Answer 3

I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.

I think the root of the trouble is that a language like $L=\{ab\}^∗$ is infinite in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a finite state automaton.

Another issue is that formal language theory is rather peculiar in how it uses the term "language".

To everybody in this world except people in formal language theory, a language is a system of utterances used to communicate, so each utterance has a form (its syntax) and some sort of meaning (its semantics). Formal language theory, at least the part that is used in computer science, is devoted to the problem of how best to define, formally, the syntax of languages. It is all about the relationship between the syntax of languages (what the utterances look like) and formalisms (languages!) such as regular expressions that are used to define the syntax of languages.

Hence, in formal language theory, 'a language' is defined simply as 'a set of strings'. It does not typically assign meanings to the strings in the language.

At the same time, the formalisms used to describe languages, such as regular expressions, also form languages in this sense: for instance, every regular expression is a string, and hence, the set of regular expressions is a language. However, for these formalisms, the strings in the language do have a meaning: for instance, the meaning of a regular expression is the language it denotes.

For instance, $ab$ is a string; hence, $\{ab\}$ is a language, namely, the language consisting of the string $ab$. However, $ab$ is not only a string, but also a regular expression: a member of the set of valid regular expressions (which is a language). Like every regular expression, it has a meaning: it denotes a language, in this case, the language $\{ab\}$.

Now let's get on to your example: $\{ab\}^*$. The operator ${}^*$ denotes a function that maps languages to languages: it maps each language $L$ to the language consisting of all strings that consist of a string in $L$ zero or more times repeated. If $L$ is the empty language, the result is $L$; in all other cases, the result is an infinite language. For instance, $\{ab\}^*$ is the language $\{ \epsilon, ab, abab, ababab, abababab, \ldots \}$. It is infinite, but using the operator ${}^*$, we can describe it in a finite way, as $\{ab\}^*$.

Furthermore, we can use a regular expression to describe this language, namely $(ab)^*$. Like all regular expressions, this is a finite string, but like most regular expressions that contain the ${}^*$ operator, it describes an infinite language.

Whenever a text on formal languages uses an expression such as $(ab)^*$ that denotes a language, ask yourself whether it is discussing the regular expression itself (e.g. how it is constructed, which language it denotes, etc.) or whether it merely uses the regular expression to refer to the language being denoted.