3
$\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$
3
  • $\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$ Commented Oct 4, 2015 at 23:59
  • $\begingroup$ @Chappers fixed $\endgroup$ Commented Oct 5, 2015 at 0:02
  • $\begingroup$ Thank you, much better! :) $\endgroup$ Commented Oct 5, 2015 at 0:03

2 Answers 2

Reset to default
6
$\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$
4
  • $\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$ Commented Oct 8, 2015 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$ Commented Oct 9, 2015 at 12:20
  • $\begingroup$ Not quite, i mean the direct product of two languages A and B $\endgroup$ Commented Oct 9, 2015 at 12:51
  • $\begingroup$ Good point at the end. Thanks @mrp $\endgroup$ Commented Jun 13, 2023 at 6:05
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$
1
  • $\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$ Commented Oct 5, 2015 at 0:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.