Exercício 16. Uma palavra y denomina-se uma permutação da palavra x se os símbolos de y podem ser reordenados para formar x. Por exemplo, as permutações da palavra x=011 são 110,101 e 011.
Se L é uma linguagem, então perm(L) é o conjunto das palavras que são permutações das palavras em L. Por exemplo, se L_{01}=\left\{0^{n} 1^{n}: n \geq 0\right\}, então perm \left(L_{01}\right) é conjunto das palavras com mesma quantidade de 0 's e 1’s. Faça o seguinte.
Dê um exemplo de uma linguagem regular L sobre o alfabeto \{0,1\} tal que perm (L) não é regular. Justifique sua resposta.
Sugestão: Tente encontrar uma linguagem regular cujas permutações sejam todas palavras com um número igual de 0’s e 1’s.
Dê um exemplo de uma linguagem regular L sobre o alfabeto \{0,1,2\} tal que perm( L ) não é L L C.
Prove que, para toda linguagem regular L sobre um alfabeto de dois símbolos, perm (L) é L L C.
Passo 1
O enunciado define, para uma linguagem L, a operação \mathrm{perm}(L) que contém todas as palavras que são permutações de alguma palavra de L. Precisamos:
Dar um exemplo de L\subseteq\{0,1\}^{*} regular tal que \mathrm{perm}(L) não seja regular.
Dar um exemplo de L\subseteq\{0,1,2\}^{*} regular tal que \mathrm{perm}(L) não seja livre de contexto.
Provar que, se L\subseteq\{0,1\}^{*} é regular, então \mathrm{perm}(L) é livre de contexto.
Para isso usaremos a definição de permutação, o lema do bombeamento (para mostrar não regular/ não CFL) e, no item 3, o teorema de Parikh e a semilinearidade dos vetores de contagem de símbolos de uma linguagem regular.
Passo 2
Item 1. Tomemos
L \;=\; (01)^{*}.
Essa linguagem é regular (autômato que repete o ciclo “lê 0, depois 1”). Quais são as permutações de uma palavra de (01)^{*}? Se uma palavra em L tem exatamente n zeros e n uns (pois é \underbrace{01\,01\,\cdots}_{n}), então \mathrm{perm}(L) contém todas as palavras sobre \{0,1\} que têm n zeros e n uns, para algum n\ge0. Logo
É conhecido que \{0^{n}1^{n}2^{n}\mid n\ge0\} não é livre de contexto; de fato intersectando \mathrm{perm}(L) com 0^{*}1^{*}2^{*} recuperamos exatamente esse padrão, o que prova que \mathrm{perm}(L) não é CFL.
Passo 4
Item 3. Seja L\subseteq\{0,1\}^{*} regular. Pelo teorema de Parikh, o conjunto dos vetores
S\;=\;\{\bigl(|w|_{0},|w|_{1}\bigr)\mid w\in L\}
é semilinear, ou seja, pode ser escrito como união finita de conjuntos lineares
S \;=\;\bigcup_{i=1}^{k}\{(c_{i0},c_{i1})+t\,(a_{i},b_{i})\mid t\ge0\}.
Cada A_{i} é livre de contexto porque podemos montar uma gramática que primeiro produz as c_{i0} cópias de “0” e c_{i1} cópias de “1” em qualquer ordem (usando regras que escolhem produzir “0” ou “1” até esgotar as cotas iniciais) e em seguida repete, via recursão, blocos que produzem a_{i} zeros e b_{i} uns em qualquer ordem. Como a união finita de CFLs é CFL, segue que
\mathrm{perm}(L)\;=\;\bigcup_{i=1}^{k}A_{i}
é livre de contexto.
Resposta
L=(01)^{*}. Nesse caso \mathrm{perm}(L)=\{w\mid|w|_{0}=|w|_{1}\}, que não é regular.
L=(012)^{*}. Aqui \mathrm{perm}(L)=\{w\mid|w|_{0}=|w|_{1}=|w|_{2}\}, que não é CFL.
Para toda L\subseteq\{0,1\}^{*} regular, \mathrm{perm}(L) é CFL, pois seus vetores de paridade são semilineares (teorema de Parikh) e cada componente linear gera uma CFL; a união finita preserva a condição de livre de contexto.