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

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.

I rather think the root problem is that formal language theory is rather sloppy in how it tends to use the term "language", and you are confusing languages with denotations for languages as a result.

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'.

So in formal language theory, strictly speaking, $ab^*$ is not a language; rather, it is a regular expression that denotes a language, namely, the set of strings that I can also indicate as follows: $\{a, ab, abb, abbb, \ldots \}$. The expression is finite, while the language it denotes is not.

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.