14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Hunter McMillen Nov 11 '12 at 1:23
  • 1
    $\begingroup$ "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). $\endgroup$ – Raphael Nov 12 '12 at 11:28
  • $\begingroup$ Why should the finite number of states be more significant than the finite description of any other machine? $\endgroup$ – babou May 23 '14 at 21:58
  • $\begingroup$ The automaton may have loops and you can use some states infinite times. $\endgroup$ – doganulus May 24 '17 at 22:02
26
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – timberly Nov 11 '12 at 20:15
  • 1
    $\begingroup$ that is correct. $L=\{a, b\}^*$ is an infinite, regular language. $\endgroup$ – Ran G. Nov 11 '12 at 21:41
  • 1
    $\begingroup$ @timberly Sure, we can know and prove what kind of language it is. $\endgroup$ – phant0m Nov 12 '12 at 19:13
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.