wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sym(L)
        
(Message started by: baudolino on Aug 31^st, 2004, 1:01pm)

Title: Sym(L)
Post by baudolino on Aug 31^st, 2004, 1:01pm

If L is a regular language over alphabet A, is Sym(L) regular?

Sym(L) is the language over the same alphabet A consisting of all permutations of the elements of L. This means that a string x of length n is in Sym(L), if there is a permutation [sigma] of the symmetric group of n elements such that the string x^[sigma], obtained by permuting the n symbols in x using the permutation [sigma], is in L.

Title: Re: Sym(L)
Post by Aryabhatta on Sep 1^st, 2004, 12:02am

Sym(L) need not be regular if L is regular. Counterexample follows:
:: [hide]

First consider the Language L_EQ of binary strings in which the number of 1's is same as the number of 0's. We can show that L is non-regular by applying the pumping lemma as follows:

Given n, pick z = 0ⁿ1ⁿ.
No matter how the adversary picks u,v, w (as constrained by the lemma) uv²w cannot be in L_EQ. So L_EQ is not regular.

Consider the language L_ALT determined by the regular expression (10)^*. (A string of 1's and 0's alternating, starting with a 1)

We have L_EQ = Sym(L_ALT), which gives us a counterexample.

[/hide]

Title: Re: Sym(L)
Post by baudolino on Sep 1^st, 2004, 8:20am

What about the converse? If Sym(L) is regular, is L regular?

Title: Re: Sym(L)
Post by towr on Sep 1^st, 2004, 8:27am

::[hide]
If Sym(L) is regular, than the strings are finite, and thus the language. And any finite language, and subset of it (L is a subset of Sym(L)), is regular.

I suppose it might even be the case that if a language is regular any subset of it must be regular as well. But I'm not going to try and prove that now.
[/hide]::

Title: Re: Sym(L)
Post by baudolino on Sep 1^st, 2004, 9:25am

towr, it is not true that if a language is regular, any subset is regular. Suppose for a second that this is true. If L is any language over the finite alphabet A, then L is a subset of A*. Since A* is regular, it would imply that L is regular as well. Of course, the nonregular L_EQ in Aryabhatta's counterexample would provide a contradiction.

Also, why would Sym(L) regular imply that Sym(L) is finite? L_ALT in Aryabhatta's counterexample is a regular infinite language.

Title: Re: Sym(L)
Post by towr on Sep 1^st, 2004, 9:48am

yes, but Sym(L) must contain any permutation of all strings in Sym(L).

meh.. I've got a few bugs to work out of my reasoning.. brb

Title: Re: Sym(L)
Post by Aryabhatta on Sep 1^st, 2004, 10:03am

on 09/01/04 at 08:20:30, baudolino wrote:

What about the converse? If Sym(L) is regular, is L regular?

This is not true too.

Consider the following Languages with binary alphabet.

L₁ = {0ⁿ1ⁿ | n [in] [bbn]}
L₂ = (1+0)^* - L₁ (the complement of L1)

L₁ is not regular by pumping Lemma. This implies that L₂ is not regular too.
We have Sym(L₂) = (1+0)^* which is regular.