1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ I always have trouble coming up with a DFA for a particular language. Any tips? $\endgroup$ – Raj Apr 22 '15 at 21:36
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 22 '15 at 21:38
  • $\begingroup$ 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? $\endgroup$ – Raj Apr 22 '15 at 21:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 22 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.