1. Example: derivatives of a regular expression

Unix/Perl format regexp:
R = [+-]?[0-9]+(\.[0-9]+)?
Regexp in basically the format we've been discussing
R = ([\+\-]+epsilon)[0-9][0-9]*(epsilon + \.[0-9][0-9]*)
note that [0-9] = 0+1+2+...+9

D_epsilon R = R
D_x R = empty set regular expression = \0
D_+ R = [0-9][0-9]*(\.[0-9][0-9]+)
D_12 R = [0-9]* (epsilon + (\.[0-9][0-9]+))

2. Example: delta

delta(R) = \0
delta(D_1 R) = 
D_1 R = [0-9]* (epsilon + \.[0-9][0-9]*)

delta(D_1 R) = epsilon & epsilon = epsilon

3. Example: building a DFA from a reg exp

R = (0 + 1)* 1

Think about the NFA:
S_epsilon : empty string or 0 or 1 or 00 or 01 or 10 or ...
S_final : whatever followed by a 1

Build the DFA in terms of derivatives:
derivative			corresponding state
D_epsilon R = R			q_epsilon

D_0 R = R			q_epsilon
D_1 R = epsilon + R		q_1

D_{10} R = D_0 D_1 R = D_0 (epsilon + R)	q_epsilon
	D_0 epsilon = doesn't match anything
	D_0 R = R

D_{11} R = D_1 D_1 R = D_1 (epsilon + R)	q_1
	D_1 epsilon = doesn't match anything
	D_1 R = epsilon + R

DFA:
q_epsilon : 0 --> q_epsilon, 1 --> q_1
q_1       : 0 --> q_epsilon, 1 --> q_1


4. Example of an equation on reg exps that would lead to a conflict for
unification, but makes sense for DFA minimization

R = D_0 R