3
$\begingroup$

In describing the tokens of a programming language using regular expressions, it is not necessary to have the $\epsilon$, (for the empty set) or t (for the empty string). Why is this?

Please tell me why is it not necessary thanks

$\endgroup$
3
$\begingroup$

The empty set is only needed in order to describe the empty regular language. The set of tokens of a certain type is never empty, so the empty set isn't needed.

Similarly, the empty string is only needed to describe regular languages which include the empty string. The empty string isn't a token of any type, so the empty string isn't needed.


Here are some proofs. I will use the convention in which $\emptyset$ is the emptyset and $\epsilon$ is the empty string. I will use the following inductive definition of regular expressions over an alphabet $\Sigma$:

  • $\emptyset$ is a regular expression.
  • $\epsilon$ is a regular expression.
  • For any $\sigma \in \Sigma$, $\sigma$ is a regular expression.
  • If $r$ is a regular expression then $r^*$ is a regular expression.
  • If $r_1,r_2$ are regular expressions then $r_1+r_2$ is a regular expression.
  • If $r_1,r_2$ are regular expressions then $r_1r_2$ is a regular expression.

Two regular expressions are equivalent if they generate the same language. We denote this by $\approx$. The language generated by $r$ is denoted $L[r]$.

Lemma 1. Every regular expression is either equivalent to $\emptyset$ or to a regular expression without $\emptyset$.

Corollary 1. If a regular expression doesn't generate the empty language, then it is equivalent to a regular expression without $\emptyset$.

Note that every regular expression not involving $\emptyset$ doesn't generate the empty language.

Proof. The proof is by structural induction. The base cases $\emptyset,\epsilon,\sigma$ are obvious. Consider now a regular expression $r$ constructed inductively from one or two regular expressions $r_1,r_2$, which we can assume satisfy the dichotomy in the lemma. If $r_1,r_2 \neq \emptyset$ then there is nothing to prove, so assume that at least one of them is $\emptyset$.

  • $r = r_1^*$: in that case $r = \emptyset^* \approx \epsilon$.
  • $r = r_1 + r_2$: if $r_1=r_2=\emptyset$ then $r \approx \emptyset$. If $r_1 \neq \emptyset$ and $r_2 = \emptyset$ then $r \approx r_1$.
  • $r = r_1r_2$: in that case $r \approx \emptyset$. $\qquad\square$

Lemma 2. Every $\emptyset$-free regular expression can be written in one of the forms $\epsilon,s,s+\epsilon$, where $s$ is $\emptyset,\epsilon$-free and $\epsilon \notin L[s]$.

Corollary 2. If $\epsilon \notin L[r]$ and $L[r] \neq \emptyset$ then $r$ is equivalent to a regular expression not involving $\emptyset,\epsilon$.

Proof. Again the proof is by structural induction. The base cases $\epsilon,\sigma$ are obvious. Let us now consider a regular expression $r$ constructed inductively from $r_1,r_2$ which are of one of the forms $s_i,s_i+\epsilon,\epsilon$, where the $s_i$ satisfy the conditions stated in the lemma.

  • $r = r_1^*$: If $r_1 = \epsilon$ then $r \approx \epsilon$. If $r_1 = s_1 + \epsilon$ or $r_1 = s_1$ then $r \approx s_1s_1^* + \epsilon$.
  • $r = r_1 + r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$ and $r_2 = s_2$ then $r$ is already of the required form. Otherwise $r \approx (s_1+s_2) + \epsilon$.
  • $r = r_1r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$, $r_2=s_2$ then $r$ is already of the required form. If $r_1=s_1$ and $r_2=s_2+\epsilon$ then $r \approx s_1s_2 + s_1$. Similarly, if $r_1=s_1+\epsilon$ and $r_2=s_2$ then $r \approx s_1s_2 + s_2$. Finally, if $r_1=s_1+\epsilon$ and $r_2=s_2+\epsilon$ then $r \approx (s_1s_2 + s_1 + s_2) + \epsilon$. $\qquad\square$
$\endgroup$
  • $\begingroup$ Thanks for you reply. Can you explain little bit about your line: "The set of tokens of a certain type is never empty, " Thanks $\endgroup$ – ALI Dec 17 '17 at 10:41
  • $\begingroup$ For any token type, there is at least one token which is of this type. Otherwise, why bother defining the type? $\endgroup$ – Yuval Filmus Dec 17 '17 at 12:03

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.