HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why is $\emptyset L = L\emptyset = \emptyset$ correct?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
emptysetwhycorrect

Problem

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

First two were ok:

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

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

  • $\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?

Solution

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

Context

StackExchange Computer Science Q#42631, answer score: 13

Revisions (0)

No revisions yet.