Re: Question on language regularity

Eric Bodden <eric.bodden@xxxxxxxxxxxxxx> writes:

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.

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.

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.

As it should, because the contructed language is, indeed, regular.

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.

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

.

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: Search for multiple things in a string
    ... > language in places. ... > Regular expressions ... None of those state that regular expressions aren't a language. ... readability is a very important part of choosing the best ...
    (microsoft.public.dotnet.languages.csharp)
  • 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)