Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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