Instructions
This problem set is due on Friday January 31, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.
Problems
- Let $E$ be a regular expression. By using the definition of regular expressions, show how to construct a regular expression $E^{(R)}$ such that $L(E^{(R)}) = L(E)^R$.
Note. For a language $L$, the language $L^R$ is the set of words that are reversals of words of $L$,
$$L^R = \{w^R \mid w \in L \}.$$
- Let $L = \{a^{k^2} \mid k \in \mathbb N\}$. Show that $L$ is not regular.
- Let $L = \{w \in \{a,b\}^* \mid w \neq w^R \}$. Determine, with proof, whether or not $L$ is regular.
Reflection
Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.
Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".
- The midterm is coming up soon. What are some things that you would like to understand better as you prepare for it?
- What are some questions about regular languages or formal languages in general (i.e. not necessarily related what we have or will cover) that you have?
- Many of you mentioned that you did not have a clear understanding of what this course is like, so it was difficult to set goals. Now that it's been a few weeks, are there any goals you have for the rest of the course? If you had already set some goals, how do you feel about your progress so far?
- Is there anything else you would like me to know at this point?