2
$\begingroup$

Wikipedia says

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?

$\endgroup$
  • $\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 Jul 22 '14 at 8:06
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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