0
$\begingroup$

I was solving this question:

Which of the following statement(s) is/are false?

  1. $L^0=\{\epsilon\}$
  2. $|L^0|=0$

The answer given was None. That is, none of these statements are false and both are true. However, I feel both are wrong. I feel

$L^1=L$ and
$L^0=\phi$

Also

$|L^0|=|\phi|=0$

Am I wrong with this?

$\endgroup$
  • $\begingroup$ We want to define $L^0 = \{\epsilon\}$ so that $L^{n+m}=L^n L^m$ holds even when one of $n,m$ is $0$. $\endgroup$ – chi Jul 15 '18 at 11:57
  • $\begingroup$ I didnt get what you mean to say. Please read below comment. $\endgroup$ – anir Jul 15 '18 at 16:41
  • $\begingroup$ I guess doing power operation on language and symbol (or string) yields different result. If it were symbol say $a$, it would have been $a^0=\epsilon$. But its languange $L$, which is a "set", not string or symbol. Note that $a^1=a,a^2=aa$. Similarly $a^0=\epsilon$. But same does not translate to $L$ directly. For more example, let $L_1=\{w|w\in (a,b)^*\}$ and $L_2=\{w^R|w\in (a,b)^*\}$, then $L_1L_2$ is regular, but $L_3=\{ww^R|w\in (a,b)^*\}$ is context free. Taking string zero times leaves back empty string $ε$, taking set (language) zero times leaves empty set (language) $\phi$. $\endgroup$ – anir Jul 15 '18 at 16:41
4
$\begingroup$

$L^0$ is defined to be $\{\varepsilon\}$. (Since a string formed by concatenating zero strings together is the empty string).

This gives the answer to the first question - which is correct.

Now, $\{\varepsilon\}$ contains exactly one string - which is the empty string. Therefore: $|\{\varepsilon\}|=1$. (The given answer is wrong).

Note that $|\{\varepsilon\}|=1\ne0=|\varepsilon|$. Also, note that $\{\varepsilon\} \ne \emptyset$.

$\endgroup$
  • $\begingroup$ I guess doing power operation on language and symbol (or string) yields different result. If it were symbol say $a$, it would have been $a^0=\epsilon$. But its languange $L$, which is a "set", not string or symbol. Note that $a^1=a,a^2=aa$. Similarly $a^0=\epsilon$. But same does not translate to $L$ directly. For more example, let $L_1=\{w|w\in (a,b)^*\}$ and $L_2=\{w^R|w\in (a,b)^*\}$, then $L_1L_2$ is regular, but $L_3=\{ww^R|w\in (a,b)^*\}$ is context free. Taking string zero times leaves back empty string $ε$, taking set (language) zero times leaves empty set (language) $\phi$. $\endgroup$ – anir Jul 15 '18 at 16:42
  • $\begingroup$ Am I right with above comment? $\endgroup$ – anir Jul 15 '18 at 16:42
  • 1
    $\begingroup$ @anir Unfortunately not. There's a reason for doing it this way, which I'll post as an answer, since it's too long for a comment. $\endgroup$ – Draconis Jul 15 '18 at 17:34
  • $\begingroup$ @Draconis What Mickey mean by $0=|\varepsilon|$ in $|\{\varepsilon\}|=1\ne0=|\varepsilon|$? (he seems to have not visiting the site for long.) Length of empty string is zero? $\endgroup$ – anir Nov 21 '19 at 6:00
  • 1
    $\begingroup$ @anir Yes, the length of the empty string is zero, but the size of the language $\{\varepsilon\}$ is one (it contains a single string, $\varepsilon$). $\endgroup$ – Draconis Nov 21 '19 at 6:09
4
$\begingroup$

Mickey's answer is completely correct. But I'd like to explain a bit more thoroughly why that's the correct answer.

At first glance, it would make sense to have $A^0 = \varnothing$: that is, the empty set. But in practice, the special cases of this operation are defined in a way that lets useful theorems hold, and letting $A^0 = \varnothing$ doesn't prove as useful as letting $A^0 = \{\varepsilon\}$.

In particular, consider the concatenation operation on languages. If we have languages $A$ and $B$, then $AB$ is the language "any string from $A$ followed by any string from $B$". It follows that you can't concatenate anything with the truly empty language $\varnothing$: $A \varnothing = \varnothing$, and $\varnothing A = \varnothing$.

In the general case, we know that $A^x A^y = A^{x+y}$. For example, $A^2 A^3 = A^5$. And this is a useful rule for various proofs. But if we say that $A^0 = \varnothing$, then this breaks down: $A^2 A^0 = A^2 \varnothing = \varnothing$ rather than $A^2$.

If instead we define $A^0 = \{ \varepsilon \}$, then the rule still holds: $A^2 A^0 = A^{2+0} = A^2$. So we choose to use this definition, because it makes our system of rules more useful in general.

There are other mathematical reasons why this is more elegant. For example, $|A^n|$ can be thought of as "the number of ways to choose $n$ elements from $A$, with replacement", and there's exactly one way to choose zero elements from any set: choosing none of them at all.

But all of these different ways boil down to: we choose to use this definition, because it makes things work out nicely. Like with anything else in mathematics, it's a conscious choice to do it this way, rather than any universal law of nature; it's just a conscious choice that leads to interesting results, and thus a choice we consider useful.

$\endgroup$
  • $\begingroup$ Now that was a bummer. So what I was saying was somewhat correct, but all of us have made choice to accept this specific definition. Do you know any reference book saying same? Is it specified in Peter Linz's or Ullman's book? Just want to read more...though your explanation sounds perfect. Just want to know more people's perspective. May be someone else also comment here adding or confirming to your answer. I am first time facing such case of accepting some definition for convinience... $\endgroup$ – anir Jul 15 '18 at 19:11
  • $\begingroup$ @anir You'd be surprised how much of mathematics involves accepting a certain definition for convenience! This is never really made clear in most classes/instructional programs, but everything in mathematics is a choice: even the fact that 1+2=3 is a specific choice made by mathematicians, and accepted by others because it turns out to be more useful than the alternatives! $\endgroup$ – Draconis Jul 15 '18 at 20:55
1
$\begingroup$

Here is yet another answer complementing to already completely correct answers. As chi and Draconis state, the key property is $L^{m+n}=L^m L^n$. As Mickey states but does not explain why, this leads to $L^0=\{\epsilon\}$. Draconis' answer apparently makes it too easy to read as an "arbitrary" choice, or even that it is an artificial choice replacing some other, "more natural" choice.1

Here's a somewhat more general perspective. Virtually always when we use the notation $x^n$ where $n$ is a natural number, we intend $x^{(-)}$ to be a monoid homomorphism from the natural numbers equipped with the additive structure. This means $x$ itself must be an element of some specified monoid. Usually, this is implicitly specified by being the one we multiplicative notation for for elements of the relevant set. The unit and operation of the additive monoid on natural numbers are $0$ and $+$. For $x^{(-)}$ to be a monoid homomorphism means $x^0=u$ and $x^{m+n} = x^m \star x^n$ where $u$ and $\star$ are the unit and operation of the specified monoid on the set containing $x$.

Now the set of finite sequences(or lists) on an alphabet $\Sigma$, often written $\Sigma^*$, is actually the free monoid2 on $\Sigma$. The unit is the empty sequence $\epsilon$ and the operation is concatenation which I'll write as $\frown$ to have it be explicit. This leads to exactly the behavior you describe on the comment to the question. That is, for words $a$, $a^{m+n}=a^m\frown a^n$ and $a^0=\epsilon$. Next, given any monoid on a set $X$, we can define a new monoid on the powerset of $X$ (those elements are subsets of $X$). If $u$ and $\star$ are the unit and operation of a given monoid on $X$, then $\{u\}$ is the unit for the operation (which I'll call $\dot\star$), $S\ \dot\star\ T =\{s\star t\mid s\in S \land t \in T\}$. (Prove this.) This is, of course, exactly the monoid structure we're using when we talk about concatenating languages (i.e. subsets of $\Sigma^*$). This immediately leads to $L^0=\{\epsilon\}$ and $L^{m+n}=L^m\ \dot\frown\ L^n$.

There are many other monoid structures we can place on the power set of $X$. For example, for any set $X$ which need not be a monoid. We have the following two monoids on the power set of $X$: 1) unit $X$ and operation $\cap$, 2) unit $\varnothing$ and operation $\cup$. (Prove that these are monoids.) If you wanted $L_1 L_2$ to mean $L_1\cup L_2$, then we'd have $L^0 = \varnothing$ and $L^{m+n}=L^m\cup L^n$, but $L_1 L_2$ usually means $L_1\ \dot\frown\ L_2$ as above for which the unit, and thus $L^0$, is $\{\epsilon\}$. Choosing $L^0$ to be $\varnothing$ while still keeping $L_1 L_2$ as $L_1\ \dot\frown\ L_2$ means $L^{(-)}$ is no longer a monoid homomorphism. This will lead to all kinds of unexpected behavior, clumsy special-cases, and missed connections.

1 Draconis' point is more that definitions can't be wrong. One is free to define things however they like no matter how clumsy, awkward, and confusing the result may be. However, some definitions are better than others.

2 Formal language theory is very much a study of various monoids and operations upon monoids. It's pretty close to just being "Monoid Theory".

$\endgroup$
  • $\begingroup$ This answer would stand by itself if you started at the word "Virtually" (2nd sentence of 2nd paragraph). If you really feel the need to retain the commentary, it should be in an endnote. But imho it adds nothing to the value of the answer. $\endgroup$ – rici Jul 16 '18 at 16:40

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.