# Proving regular languages

I am given the language L = {a,b}* and a/L = { w ∈ {a,b}* | aw ∈ L }. I am trying to prove that that if L is regular so is a/L. My approach so far is the prove that L is regular (using pumping lemma) and since a/L is a subset of L, then a/L must also be regular. I am having trouble doing the pumping lemma on L? What is an example string S I can use?

• Regular languages aren't closed under set containment. – symplectomorphic Apr 22 '15 at 21:30

## 1 Answer

HINT: The pumping lemma cannot be used to prove that a language is regular: it can only be used to show that a language is not regular. I suggest starting with a DFA that accepts $L$ and showing how to modify it to get an DFA that accepts $a/L$; the required modification is very simple.

• I always have trouble coming up with a DFA for a particular language. Any tips? – Raj Apr 22 '15 at 21:36
• @Raj: You can’t come up with a specific one here, because you don’t know what regular language $L$ is. Just imagine that you have a DFA $M$ that accepts $L$: it has a state set, an initial state, and so on. There’s a very simple change that can be made to it, one that can be described without knowing the details of $M$, that will turn it into a DFA that accepts $a/L$. – Brian M. Scott Apr 22 '15 at 21:38
• Please help me a little further. I am completely new to proving regular languages and DFAs. The change I can think of making to M to accept a/L would be having w in it? – Raj Apr 22 '15 at 21:51
• @Raj: No: $w$ stands for any string of $a$s and $b$s. It’s very hard to say much more without simply doing the problem, but here’s a further hint: the only change needed is a change in the initial state. You want the the modified DFA to treat an input of $w$ as if it were an input of $aw$. – Brian M. Scott Apr 22 '15 at 21:54