The empty language, i.e., the language that contains no strings can be recognised by a DFA (any DFA with no accepting states will accept this language), but it can not be defined by any regular...

The empty language, i.e., the language that contains no strings can

be recognised by a DFA (any DFA with no accepting states will accept this language), but it can not be defined by any regular expression using the constructions in

Sect. 1.1. Hence, the equivalence between DFAs and regular expressions is not complete. To remedy this, a new regular expression φ is introduced such that L(φ) = ∅.

We will now look at some of the implications of this extension.

a) Argue why each of the following algebraic rules, where s is an arbitrary regular

expression, is true:

φ|s = s

φs = φ

sφ = φ

φ∗ = ε

b) Extend the construction of NFAs from regular expressions to include a case

for φ.

c) What consequence will this extension have for converting the NFA to a minimal

DFA? Hint: dead states.