Giving a regular language $L$ so that $K_L = \{x\,|\,∃y\,|\,(x \sim y \,\land\, y \in L)\}$ is not regular

48 Views Asked by At

Let $\{a,b\}$ the alphabet $\Sigma$. The relation $\sim$ is defined on $\{a,b\}^*$ by $x \sim y$ if $x$ and $y$ have the same number of a's and b's. If $L$ is a language on alphabet $\Sigma$ then $$K_L = \{x\,|\,∃y\,|\,(x \sim y \,\land\, y \in L)\}$$ So, from my understanding, a word $x \in K_L$ if it can be rearranged to form a word from $L$. But what kind of language $L$ can be given so that $K_L$ is non regular ? I can't seem to find an answer to that.

1

There are 1 best solutions below

2
On BEST ANSWER

The language $\{\epsilon,ab,abab,ababab,\ldots\}$ is regular ($S\to abS\mid\epsilon$) but the set of all words that have the same number of $a$'s and $b$'s isn't.