@ericbodden: "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"
    @ericbodden: "<quote>
Hmm, I don't think so. I am not sure how to define the output function
in that case.
Another attempt I made was trying to define a translation function on
the defining regular expression. That may maybe work...
If not, could first/follow-sets help maybe?
Eric"
    @torbenm: "Eric Bodden <email_address> writes:
<quote>
When such questions are asked in exam questions, they usually mean "is
the following guaranteed to be regular?".  So finding a single example
where it is regular isn't enough.  If, on the othe rhand, you could
find a single example where the contructed language isn't regular,
that would be enough to prove the proposition false.
As it should, because the contructed language is, indeed, regular.
The approach is right.  Taking the DFA for L, make it do two steps at
once by following two sequential characters in a single transition.
Basically, from each state find all the possible two-step transitions.
This yields a new DFA with pairs of characters on transitions.  Now,
swap each such pair to get a new DFA.  Make this into an NFA for the
original alphabet by inserting a state between the two characters on a
transition.
        Torben"
{'source': 'USENET', 'other_information': '{"reply_count": 2, "forum_name": "comp.theory.20140624.mbox"}', 'file': 'data/output/usenet-comp.theory.parquet'}