What's the difference between phi and lambda in regular expression?

Question

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$?

Answer 1

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$?