principleMajor
Infinite Language vs. finite language
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.
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 $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.,
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.