Author |
Topic: Sym(L) (Read 882 times) |
|
baudolino
Guest
|
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.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Re: Sym(L)
« Reply #1 on: Sep 1st, 2004, 12:02am » |
 Quote  Modify
|
Sym(L) need not be regular if L is regular. Counterexample follows:
::
First consider the Language LEQ 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 = 0n1n.
No matter how the adversary picks u,v, w (as constrained by the lemma) uv2w cannot be in LEQ. So LEQ is not regular.
Consider the language LALT determined by the regular expression (10)*. (A string of 1's and 0's alternating, starting with a 1)
We have LEQ = Sym(LALT), which gives us a counterexample.
|
|
IP Logged |
|
|
|
baudolino
Guest
|
What about the converse? If Sym(L) is regular, is L regular?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sym(L)
« Reply #3 on: Sep 1st, 2004, 8:27am » |
Quote Modify
|
::
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.
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
baudolino
Guest
|
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 LEQ in Aryabhatta's counterexample would provide a contradiction.
Also, why would Sym(L) regular imply that Sym(L) is finite? LALT in Aryabhatta's counterexample is a regular infinite language.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sym(L)
« Reply #5 on: Sep 1st, 2004, 9:48am » |
Quote Modify
|
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
|
| « Last Edit: Sep 1st, 2004, 9:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sym(L)
« Reply #6 on: Sep 1st, 2004, 10:03am » |
Quote Modify
|
on Sep 1st, 2004, 8:20am, 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.
L1 = {0n1n | n [in] [bbn]}
L2 = (1+0)* - L1 (the complement of L1)
L1 is not regular by pumping Lemma. This implies that L2 is not regular too.
We have Sym(L2) = (1+0)* which is regular.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove