- 0 (0 + 1)* 1
- (1* 0 1* 0 1* 0 1* 0 1* 0 1*)* 1*
- you can't do this with a regular expression. How can you tell? the
clue is that this language requires counting. Regular expressions can't
'count' because FSA's can't count.
- This one is harder.
(1 + 0*) (0 + 01)*
(The first part allows strings starting with a 1. The 0* term
serves two purposes: it allows strings starting with a 0,
and the empty string is now accepted. The second part prevents
two consecutive 1's from appearing)