I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator.

Let swap : {a, b}∗ → {a, b}∗ be the function that exchanges the a’s and b’s in a string. For example, swap(baaba) = abbab and swap(aaaa) = bbbb. For L a language over {a, b}, define swap(L) as follows: swap(L) = {swap(w) | w ∈ L}.

Show that the class of regular languages over {a, b} is closed under the swap operator. Let M = (Q, {a, b}, δ, q0, F) be a DFA. Define DFA M' such that L(M' ) = swap(L(M)).

So far I have M' = (Q, {a, b}, δ', q0, F) where δ'(q, a) = δ(q, b) and δ'(q, b) = δ(q, a) meaning that in the transition function states q given a that map to q in M would map to q given b in M'. Am I missing anything?

  • 1
    $\begingroup$ What did you try? Where did you get stuck? If you're not sure what to try, you might start working through some examples (pick a simple language with a simple DFA, and try to solve it for that language, and repeat until you get some intuition). We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 12 '18 at 19:11
  • 5
    $\begingroup$ Do you have a more specific question about your attempt? If you do, I suggest you edit your question to articulate it, and show your work. If you have a candidate solution and want to know whether it is correct, the way to tell is to either prove it correct or find a counterexample, so I suggest you try that. Proof by induction might be useful. A good first step is to work through some examples and see if it works correctly for all those examples. Make sure to read the link I gave in its entirety -- we wrote it to try to help folks get the most benefit from this site. $\endgroup$ – D.W. Feb 12 '18 at 20:23

Your Answer

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

Browse other questions tagged or ask your own question.