12
$\begingroup$

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular operations (concatenation, union, and star) for that to hold.

For example, I have been told that if I can only use the union and concatenation regex operations (2 out of the 3), there would be a regular language I can't describe with just those two.

Same with just Kleene star and union. What are some examples of this?

Improve this question
$\endgroup$
19
$\begingroup$

With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only concatenation and the Kleene star, you can't describe a language such as $L = \{a,b\}$.

Improve this answer
$\endgroup$
  • 3
    $\begingroup$ .... and $\{a,b\}$ is not possible without union. $\endgroup$ – Raphael♦ Feb 1 '16 at 15:30
  • $\begingroup$ So why can't I described L={a,b} without union? Is it because they can't be represented as separate elements with star and concatenation? It could only do ab, bb, aba etc.? $\endgroup$ – user3295674 Feb 1 '16 at 23:53
  • $\begingroup$ @user3295674 Exactly. $\endgroup$ – DylanSp Feb 2 '16 at 2:07
  • $\begingroup$ and something like L={a*} would not be possible with just union and concatenation, right? Thank you so much! $\endgroup$ – user3295674 Feb 2 '16 at 4:16
  • $\begingroup$ I don't even understand how star would be defined without concatenation being available. $\endgroup$ – G. Bach Feb 2 '16 at 12:46
11
$\begingroup$

A perhaps more interesting question is that of star height. The other answer mentions that if you can't use star, then you can only generate finite languages. What if you are not allowed to nest stars (so something like $(a^*b^*c)^*$ is not allowed)? What if you are only allowed to nest stars two levels deep? $d$ levels deep? It turns out that for every $d$ there are regular expressions expressible in nesting $d$ but not in nesting $d-1$. The link contains some examples.

Improve this answer
$\endgroup$
4
$\begingroup$

Another interesting case arises by allowing complementation as a possible operation. Using union, concatenation and complement (but no star), one can obtain the language $A^*$ as the complement of the empty language. One can also obtain languages like $(ab)^*$ and $(a(ab)^*b)^*$ (not so easy to see if you don't know the trick), but there is no way to obtain $(aa)^*$.

If one now allows to use star, but not nested stars, then it is an open problem (for at least 45 years) to know whether one can obtain all regular languages. This question is known as the generalized star height problem. It is similar to the star height problem mentioned by Yuval Filmus, with the difference that complementation is now allowed.

Improve this answer
$\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.