Question on language regularity

Hi all.

While preparing for my comprehensive exam I came across this old exam
question here that really makes me suffer. It looks easy at a first
glance but then it turns out to be rather tricky...

"Let L be a regular language. Is the following language regular?
R_L := {a_2 a_1 a_4 a_3 ... a_(2n) a_(2n-1) | a1 a2 a3 ... a_(2n) in
L}"

So given a language L is the language of all even words in L where
each two letters have been switched also regular?

My first thought was "no, non-regular". But then I found a very easy
example for L where R_L is regular: Let L = {} then R_L = {}, which is
regular. So in general, R_L cannot be non-regular.

Then, however I thought that at least for certain Ls it must be non-
regular. So I tried to apply the pumping lemma. However doing so, I
failed.

So my next idea was "ok, maybe it is actually always regular". This
would probably mean to do some automaton transformation on the DFA or
NFA for L but I was unable to come up with one that would work in
general and yield the correct R_L.

Does anybody have any idea how to approach this?

Thanks a lot,
Eric

.

Relevant Pages

  • Re: Armenian, Sumerian, Burushaski, and Turkic languages
    ... indicating the importance of finding regular changes. ... There are certainly plenty of known regular correspondences ... Note that due to sporadic language change, ... sound changes, large variance in what counts as "similar"), you're ...
    (sci.lang)
  • Re: American as creolish [was] Re: Baltic Is Gothic
    ... > language and language evolution. ... Forming "regular" preterits, participles, and plurals in English ... > introduces redundancy with formal tokens. ... expressions became "normal", driving out the old expressions with no ...
    (sci.lang)
  • Re: RegExp as Finite State Machine
    ... but not regular, if I'm not mistaken -- with the Regular Expression ... The language recognized by the regexp above is actually not even ... If all Javascript regexps can be implemented using only finite state ... subset of Finite State Machines. ...
    (comp.lang.javascript)
  • Re: Reguar expression - what with *
    ... Which of the pieces does not belong to the language a*? ... It does not contain bbb but is not in your regular expression. ... automaton for the complement looks the same with final states becoming ...
    (sci.math)
  • Re: Reguar expression - what with *
    ... Which of the pieces does not belong to the language a*? ... It does not contain bbb but is not in your regular expression. ... automaton for the complement looks the same with final states becoming ...
    (sci.math)