Infinite language can not be regular? What is the final language?

Question

I read this in a book on computability:

(Kleene's theorem). A language is regular if and only if it can be obtained from finite languages ​​by applying three unions of operations, concatenation, and repeating a finite number of times.

I struggle with "final languages".

Consider this language: L = a*

This is not of course. This is the set {0, a, aa, aaa, ...} , which is obviously an infinite set ( 0 = empty string).

So this is an endless language, isn't it? That is, "infinite set" means "infinite language", right?

Clearly, a* is a regular language. And this is an endless language. Thus, by Klein's theorem, it cannot be a regular language. Contradiction.

I'm confused. I think I do not know what the "final language" means.

Answer 1

You're on the right track, it could be clearer. Kleien's theorem expresses the equivalence of three statements

Language is regular == Language can be expressed by regular expression == Language can be expressed by state machines.

Your example is indeed a common language. The final language is what you expect from it, a language that can be specified over a finite period of time.

When they talk about repetition, they talk about the Kleen Star operation, which is what a* represents, the set {empty, a, aa, aaa, aaaa, ...}

EDIT:

I found this link: Kleins theorem that helps quite a bit. This "repetition" means "Klin star", then the original statement makes sense. a* - Kleen_Star(a)

Answer 2

In the near future, your statement says:

A language is regular if and only if there is a regular expression for it.

---

"Can be obtained from finite languages ​​using three operations of combining, concatenating, repeating a finite number of times" part is essentially a quick verbal definition of a regular expression. Typically, a regular expression (RE) is formally defined starting with the following basic cases:

• ∅ (empty set) is RE
• ε (empty string) is RE
• a is RE, where a is in the alphabet

These are all finite languages. Then we get the other REs, applying the following three recursive rules finitely many times:

• A | B is RE where both A and B are REs
• AB is RE, where both A and B are REs
• A * - RE, where A - RE

---

In the end, you can create endless languages ​​using finite descriptions (regular expression).

Answer 3

The final language is a language containing a finite number of words. The simplest cases are those that do not contain words at all, an empty line and one line consisting of one character (for example, a in your example).

I think your confusion stems from a misunderstanding of the rule you are quoting (as well as some of those who comment on the question).

(Kleene's theorem). A language is regular if and only if it can be obtained from finite languages ​​using three unions of operations, concatenation, and repeating a finite number of times.

The passage does not talk about the number of operations on lines needed to create all the lines in a language, but about the number of operations in simpler languages ​​needed to define a specific language. You mentioned language is built, starting with the final language (set {"a"}) and applying the repetition operator once.

Another and less direct way to put an end will not involve languages ​​and operations on languages, but expressions denoting languages ​​and more complex expressions combining them: a language is regular if and only if it can be denoted by a regular expression containing a finite number of operators.

Take an expression like a , denoting a finite language containing only one word "a". We can add a single repetition operator to this expression, and we get a* , an infinite language containing all concatenations of zero or more words from the first language. We can construct each finite expression E based on expressions denoting finite languages ​​and combining one or two smaller expressions F and G using the patterns E = F | G, E = FG, or E = F * will denote the correct language. Expressions denoting final languages ​​(languages ​​with a finite number of words) are the main case when a rule is expressed in expressions; final languages ​​are the basic case when the rule is specified directly in terms of languages, without any bypasses in the field of expression.

If we allow combining, concatenation, and repetition to apply infinitely many times (or, what is the same, if we allow infinite expressions using the rules for regular expressions), the resulting language is not guaranteed to be regular. It is an analogue at the level of a regular observation language that infinitely large context-free grammars can define non-contextually free languages, as evidenced by Van Wingharden's grammar.

Answer 4

infinite language means a set having infinite equivalence classes. However, a * has only one equivalence class, which makes it the final language.