I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.

But I don't know what is the difference between $\phi$ and $\lambda$.
Of course, I know $\lambda$ means the empty string, so that $\lambda s=s\lambda$.
And the textbook explains the meaning of $\phi$ is the empty set.
And more, the textbook explains that $\phi$ can be accepted by a deterministic finite automata $\left< Q, \Sigma, \delta, q_0 , F \right>$ in which $Q=\{ q_0, q_1 \}$, $\forall a \in \Sigma:\delta(q_0,a)\text{ is not defined}$, and $F=\{q_1\}$.

So, I guess the meaning of the $\phi$ is the rejected string.

But How can the expression $(\phi *)*$ mean $\lambda$?
And what's the meaning of the expression $a\phi$?


You need to distinguish between regular expression syntax and its interpretation aka semantics.

  • "$\lambda$" is a symbol representing the set that contains only the empty string $\{\varepsilon\}$).
  • "$\phi$"¹ is a symbol representing the empty set of strings $\emptyset = \{\}$.

The difference becomes apparent when you compute the interpretation $i$ of a regular expression:

  • $i(a\lambda) = i(a) \cdot i(\lambda) = \{ a \} \cdot \{ \varepsilon \} = \{a\}$

    Note: I'm deliberately using $\varepsilon$ to denote the "real" empty string outside of a regular expression. Your source probably uses $\lambda$ for both; that obscures the fact that it's used in two different ways.

  • $i(a\phi) = i(a) \cdot i(\phi) = \{a\} \cdot \emptyset = \emptyset$.

If you don't follow that last line, revisit the definition of the concatenation of languages:

$\qquad\displaystyle A \cdot B = \{ a \cdot b \mid a \in A, b \in B\}$.

  1. Do they really use $\phi$?
  • 2
    $\begingroup$ As an answer to your footnote/question. No. I quote from Linz: "$\varnothing$ is aregular expression denoting the empty set". And you are right about your assumption in your note: "$\lambda$ is a regular expression denoting $\{\lambda\}$". $\endgroup$ – Hendrik Jan Jan 3 '20 at 19:35
  • $\begingroup$ why $\lambda$ is defined to be a set? so your $\epsilon$ is a real empty string since it's not a set? $\endgroup$ – Ning Mar 17 '20 at 3:20
  • $\begingroup$ @Ning Notice the difference between $\lambda$ and $i(\lambda)$. $\endgroup$ – Raphael Mar 23 '20 at 0:06

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.