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?

Raphael
73.4k31 gold badges184 silver badges406 bronze badges
asked Jul 19, 2014 at 0:16
$\endgroup$
1
  • $\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$ Commented Jul 22, 2014 at 8:06

1 Answer 1

11
$\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.

answered Jul 19, 2014 at 0:36
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.