The collection of regular languages over an alphabet Σ is defined recursively as follows:
- The empty language Ø is a regular language.
- For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
- If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
- No other languages over Σ are regular.
I think that if it is closed under concatenation, then it must be closed under Kleene star, because we can take B to be A. So the definition can be without being closed under Kleene star?
-
$\begingroup$ If you do not allow the star operation, you cannot obtain the language containing only the empty word. This language is equal to $\emptyset^*$. $\endgroup$J.-E. Pin– J.-E. Pin2014年07月22日 08:06:25 +00:00Commented Jul 22, 2014 at 8:06
1 Answer 1
No. Closure under concatenation means that, if $A$ and $B$ are regular languages, then so is the language of strings formed by concatenating taking one string from $A$ and one from $B$. Closure under Kleene star means that, if $A$ is a regular language, then so is the langauge formed by taking any finite number of strings from $A$ and concatenating them.
If you delete Kleene star then every regular language would be finite. The reason is that any given regular language must be formed by a finite number of operations from the basic languages ($\emptyset$ and singletons). But any language whose definition involves no Kleene stars and only $k$ concatenations can only contain strings of length at most $k,ドル so it must be finite (it has at most $|\Sigma|^k$ strings in it).
Since there are infinite regular languages, the languages formed without Kleene star are a strict subset of the regular languages.
Explore related questions
See similar questions with these tags.