Regular languages that can't be expressed with only 2 regex operations

Problem Detail: 

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?

Asked By : user3295674

Answered By : DylanSp

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52556