2
$\begingroup$

I know that in set theory, $\forall A:\emptyset \subseteq A$

My question is, does this apply to formal languages? In my mind, formal languages are just a set of strings that are over some set of letters, which can be looked at as a set of strings with size 1. If I look at it strictly from the formal language side, all non-empty alphabets cannot have an "empty" letter and there would not? be an empty set in every language. Note I am not looking at the set containing only the empty string, which I understand is not in every language.

However, would a predicate $P(w)=w\in AB \iff \exists a:\exists b:a \in A \land b \in B \land ab=w$ that tests the membership of string $w$ in the concatenation of two finite (non empty) formal languages ($A,B$) always be true if there is no string $w$ at all ergo $w$ is the empty set? I think but am not sure if it is just vacuously true that if there is no string at all, $P$ would be true by the fact that $\forall A:\emptyset \subseteq A$ is vacuously true, so for any set product $\forall A:\forall B:\emptyset \subseteq AB$ would also be vacuously true

Perhaps my confusion is due to misunderstanding the empty set with regards to language theory.

$\endgroup$
  • $\begingroup$ Can we all just call it "the empty set", please? That is completely unambiguous, where as a "null set" has several meanings, and the usual meaning is much more general than just "no elements". $\endgroup$ – Chappers Oct 4 '15 at 23:59
  • $\begingroup$ @Chappers fixed $\endgroup$ – rpg711 Oct 5 '15 at 0:02
  • $\begingroup$ Thank you, much better! :) $\endgroup$ – Chappers Oct 5 '15 at 0:03
2
$\begingroup$

Languages don't contain sets, they contain strings, It's true that for any language $L$, we have that the empty set is a subset of $L$, i.e. $\emptyset \subseteq L$, since this is true of any set. So if this is what you're asking, then yes, that is trivially true.

However, if you're asking whether $\emptyset \in L$ for every language, then this question doesn't really make sense, since languages don't contain sets. The analogous notion is the empty string $\varepsilon$, so it makes sense to ask whether $\varepsilon \in L$ for any language $L$, but the answer is of course no.

$\endgroup$
  • $\begingroup$ To make sure I understand you, if $\emptyset \subseteq L$, the substitution L=AB $\emptyset \subseteq AB$ must also be true? Thanks for the answer. $\endgroup$ – rpg711 Oct 8 '15 at 17:22
  • $\begingroup$ @rpg711 Well, yes, but I think there is still some confusion. I assume that by $AB$ you mean the language (set) of all strings of length two where the first symbol is from some alphabet $A$ and the second symbol is from alphabet $B$. Then, yes, if you can show that $L = AB$, then $\emptyset \subseteq AB$, but notice that this is also true even if $L \neq AB$. As long as $AB$ is a set (and all languages are sets of strings), we have $\emptyset \subseteq AB$. $\endgroup$ – mrp Oct 9 '15 at 12:20
  • $\begingroup$ Not quite, i mean the direct product of two languages A and B $\endgroup$ – rpg711 Oct 9 '15 at 12:51
0
$\begingroup$

If you dissect the right hand side, $\exists a \in A \colon a \in A$ is false if $A = \emptyset$, so $P(\omega)$ isn't true in such a case. Unless I don't understand at all what you are asking...

$\endgroup$
  • $\begingroup$ Sorry, I was not clear enough in my question. A and B are some finite languages, and I would like to test the membership of the empty set in the concatenation AB so essentially, I am wondering if it follows that if for any set A, $\forall A: \emptyset \subseteq A$, then would it follow that for any two non-empty, finite languages, $\forall A: \forall B: \emptyset \subseteq AB$ $\endgroup$ – rpg711 Oct 5 '15 at 0:02

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.