# Infinite Language vs. finite language

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.

-
It is infinite because the ab* (Kleene star) means that you can have zero or more combinations of the string ab, this includes a potential infinite number of strings: {"", ab^1, ab^2, ab^3, .... , ab^n}. You can however still build a FSM that recognizes this language because there is no way in reality to generate an infinite string, when processed by a machine all of the strings have to be finite, but that doesn't make the language itself finite. The languages infinite-ness is theoretical. – Hunter McMillen Nov 11 '12 at 1:23
"Finitely describable" and "finite" are not the same. For example, your regular expression $\{a,b\}^*$ is a finite description of an infinite language; a finite automaton is just another one (but it's called finite automaton not because it's a finite description, but because it can store only a constant amount of bits). – Raphael Nov 12 '12 at 11:28
Why should the finite number of states be more significant than the finite description of any other machine? – babou May 23 '14 at 21:58

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

-
Thanks Ran! So just to be clear, $L=\{a\mid b\}^*$ is an infinite language? So I guess, given an infinite language, nothing can be known about what class of language it is. – timberly Nov 11 '12 at 20:15
that is correct. $L=\{a, b\}^*$ is an infinite, regular language. – Ran G. Nov 11 '12 at 21:41
@timberly Sure, we can know and prove what kind of language it is. – phant0m Nov 12 '12 at 19:13

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

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.

-

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

-