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.
  1. 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.
  2. Dê um exemplo de uma linguagem regular L sobre o alfabeto \{0,1,2\} tal que perm( L ) não é L L C.
  3. 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:
  1. Dar um exemplo de L\subseteq\{0,1\}^{*} regular tal que \mathrm{perm}(L) não seja regular.
  2. Dar um exemplo de L\subseteq\{0,1,2\}^{*} regular tal que \mathrm{perm}(L) não seja livre de contexto.
  3. 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
\mathrm{perm}(L)\;=\;\{\,w\in\{0,1\}^{*}\mid |w|_{0}=|w|_{1}\,\}.
Esse conjunto é clássico não regular (pode-se aplicar o lema do bombeamento). Portanto escolhemos L=(01)^{*}.

Passo 3

Item 2. Tomemos
L \;=\; (012)^{*}
sobre o alfabeto \{0,1,2\}. Cada palavra em L tem, para algum n, exatamente n símbolos “0”, n símbolos “1” e n símbolos “2”. Assim
\mathrm{perm}(L)\;=\;\{\,w\in\{0,1,2\}^{*}\mid |w|_{0}=|w|_{1}=|w|_{2}\,\}.
É 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\}.
Para cada i, considere a linguagem
A_{i}\;=\;\{\,w\mid (|w|_{0},|w|_{1})\in\{(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

  1. L=(01)^{*}. Nesse caso \mathrm{perm}(L)=\{w\mid|w|_{0}=|w|_{1}\}, que não é regular.
  2. L=(012)^{*}. Aqui \mathrm{perm}(L)=\{w\mid|w|_{0}=|w|_{1}=|w|_{2}\}, que não é CFL.
  3. 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.

Exercícios relacionados