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

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$$?
• 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\}$". – Hendrik Jan Jan 3 '20 at 19:35
• why $\lambda$ is defined to be a set? so your $\epsilon$ is a real empty string since it's not a set? – Ning Mar 17 '20 at 3:20
• @Ning Notice the difference between $\lambda$ and $i(\lambda)$. – Raphael Mar 23 '20 at 0:06