Class Work 6: Regular Expressions

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Grading Notes:

• Submit one answer per group.
• Make sure that the answer is legible.
• Include the full names of all group members on your submitted work (so all get credit).

Assume Σ_D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

1. Write a regular expression for all 2 digit numbers.
2. Explain in words what the following regular expression represents:
   Σ_D* / Σ_D
3. Explain in words what the following regular expression represents:
   Σ_D / Σ_D
4. Explain in words what the following regular expression represents:
   Σ_D* / Σ_D*
   where the alphabet has been extended to include the token: "/"
5. Explain in words what the following regular expression represents:
   {+,-,ε} Σ_D . Σ_D*
   where the alphabet has been extended to include the tokens: {., +, -}