Proving that a language is regular

Question

The question is as follows: given a regular language L prove that the following languages are regular :

a) All the words (x XOR y) (x and y are words in the language)

b) All the words xy s.t. yx is a word in the language

For a) I have a vague idea on how to build a NFA that would accept the language, but for b) I'm clueless. I would appreciate any help!

Answer 1

It is not a matter of defining an automaton recognising the language. Regular languages are closed under the reverse operation: if L is regular, then L^R is regular.

The general idea of the proof is that, given the automaton that recognises L, you can transform it into an automaton that recognises L^R by reversing the transitions.

Answer 2

I suppose this is homework, but one way to get started is to assume you have the prefix grammar for L and consider how to rewrite it to generate language (b).