5
$\begingroup$

I am taking a course on Automaton where I faced the algebraic laws of regular expressions.

First two were ok:

  1. $\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language gives the language $L$ itself.

  2. $\epsilon L = L\epsilon = L$: Concatenation of empty string with strings belonging to certain language $L$ gives back the set of string of language $L$

But the third one is confusing me:

  1. $\emptyset L = L\emptyset = \emptyset$

I felt it should be $\emptyset L = L\emptyset = L$, since concatenation of strings of language L with string of empty language which is essentially no strings at all (which essentially means nothing to concatenate), should give back the language $L$ itself. Where I am thinking wrong?

$\endgroup$
  • 1
    $\begingroup$ One important thing you should notice: the fact that you are dealing with regular sets represented by regular expressions is irrelevant. The only thing that matters is that they can be understood as languages, i.e. sets of strings, but not that they are regular languages. $\endgroup$ – babou May 16 '15 at 15:19
8
$\begingroup$

$L_1L_2$ means the set of all strings you can make by choosing one from $L_1$ and one from $L_2$ and concatenating the two strings. So how many ways can you choose a string from the empty set of strings and one from $L$? None at all! So there are no such concatenations and $\emptyset L = \emptyset$.

The key point is that $\emptyset$ is the language that contains no strings at all. The empty string is a string (it's the string with no letters at all) so the empty string is not a member of the empty language: $\{\epsilon\}\neq\emptyset$.

$\endgroup$
8
$\begingroup$

Just to complete David's nice answer with a simple observation:

Since $$ L_1L_2 =\{ uv \mid u\in L_1, v\in L_2\},$$

then, the size of this new language admits $$ |L_1L_2| \le |L_1|\cdot|L_2|$$ because, for each word in $L_1$ we add $|L_2|$ words to $L_1L_2$. Maybe some of the new words were already added before, which causes the inequality.

Then, it is immediate that $|\emptyset L| \le 0\cdot |L| \le 0$, thus $\emptyset L$ must be the empty language.

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