1.

a) If L is a language and a is a symbol, then the language denoted as L/a is defined as follows: L/a = { w | wa L} Informally put, L/a can be generated from L as follows: enumerate at all the strings in L that end with the symbol a, then remove that a from those strings, and output the rest of the strings. For example, if L = {0, 001, 100}, then L/0 = {, 10} and L/1 = {00}.

The question for this problem is as follows: If you are given that L is regular, then show that L/a is also regular. Your proof should be generic (i.e., not based on any specific example), just like we proved for other closure properties in the class. For instance, you can think of describing a construction procedure that takes as input a DFA for any given regular language L and converts it into a finite automaton for L/a.

b) Now, let us define another language called a\L as follows: a\L = { w | aw L} For example, if L = {0, 001, 100}, then 0\L = {, 01} and 1\L = {00}. Using the result proven in part (a) and any other closure properties of RLs already proven in class, show that a\L is regular if L is regular.