Week 4

I presented extra materials (derivative of regular expressions, following a simplified version of Brzozowski's paper; ask me if you want a copy of this paper) with the notion of abstract states and proofs that some languages are not regular


Chapters 3.2, 3.3, 3.4, 4.1, 4.2

Slides for the course

See here and an updated version here

Recommended exercises

Exercises 3.2.4 and 3.2.5 with the method of abstract states (compute directly a DFA)

Exercises 3.4.1, 3.4.2, 3.4.3

Exercises 4.1.1 c, e with the method of abstract states

Exercises 4.2.1, 4.2.2, 4.2.3, 4.2.4, 4.2.5, 4.2.15, 4.2.17

Apply the method of the slides to test if abab is in the language defined by a(ba)*? (ab)*? a(ba)*b?

Compute the derivatives 0\E, 1\Ewhere E = F01F and F = (0+1)* and 0\E, 1\E, 00\E, 01\E, 10\E, 11\E where E = (01+10)*, E = (101)*

Prove that the derivative a\E* is equal to (a\E)E* and that a\(EF) is (a\E)F is epsilon is not in E and (a\E)F + a\F if epsilon is in E