HiveBrain v1.2.0
Get Started
← Back to all entries
principleMajor

Infinite Language vs. finite language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitefinitelanguage

Problem

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.

Solution

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:

  • a finite language is any set $L$ of strings, of finite cardinality, $|L|



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

Context

StackExchange Computer Science Q#6609, answer score: 33

Revisions (0)

No revisions yet.