1. Prove countable by finding the 1-1 and onto correspondence with the natural number N

1. Strings over {a, b). that begin with a
2. Strings over {a,b} with even number of as
3. How many languages over {a,b} are there that only contain strings with an even number of as and an even number of bs?

2. Some regular expressions are easy to write; some hard.

a. Write a regular expression for strings over {a,b} that end aab

b. In class we wrote this expression for stings NOT containing the substring aab

a* | b*a* | (b*ab*aa*)*

The a* is not needed -- can just be dropped. Why?

Can you think of a string that should be generated and is not? If so, what?

Can you think of a string that this generates which is not legal? If so, what?

1. Can you find a correct expression for string NOT containing aab? If so, what is it?