As operações de fechamento, ou operações de fecho, sob linguagens regulares, podem ser definidas como aquelas que, quando aplicadas a elas, produzem uma nova linguagem também regular. Considere as informações a seguir: Dada uma linguagem regular L = {00, 01, 11, 011} sob Σ = {0, 1}. Analise as cadeias a seguir e informe quais fazem parte da linguagem L*: 1- 00011100011 2- 00111010000 3- 11010001111 4- 01101000100 5- 11011110111 Selecione a resposta:

Em $L^*$, uma cadeia pertence à linguagem se puder ser decomposta (concatenada) em zero ou mais “blocos” que pertençam a $L=\{00,01,11,011\}$.

Vamos testar cada cadeia, tentando segmentar apenas com esses blocos.

1) 00011100011 Uma decomposição possível é:

• $00\,|\,01\,|\,11\,|\,00\,|\,011$ Todos os blocos estão em $L$. Logo, 1 ∈ L*.

2) 00111010000 Começando por $00$ (ok), sobra 111010000.

• Podemos fazer $11$ (ok), sobra 1010000. Agora a sobra começa com 10, e não existe bloco em $L$ que comece com 10 (os possíveis começos são 00, 01, 11, ou 011 que também começa com 01). Logo, não há como continuar a decomposição. Portanto, 2 ∉ L*.

3) 11010001111 A cadeia começa com $11$ (ok), sobra 010001111. A sobra começa com 010....

• Se tentarmos $01$ (ok), sobra 0001111.
  • $00$ (ok) sobra 01111.
  • $011$ (ok) sobra 11.
  • $11$ (ok) sobra ε. Até aqui parece dar certo, mas note que após $11|01$ a cadeia original fica: $11\,01\,000\,1111$; e o trecho 000 não pode ser gerado por blocos de tamanho 2 ou 3 sem sobrar 0 isolado (as possibilidades são $00$ ou $01$), e a tentativa acima força uma leitura que não preserva a ordem correta dos bits (ao encaixar $00$ e depois $011$ há conflito na fronteira do terceiro 0 com o início do 011 em algumas segmentações possíveis). Testando sistematicamente: após $11$, o prefixo restante é 010... e as únicas escolhas iniciais são $01$ (sobra começando com 0) ou $011$ (mas não casa, pois seria 011 e temos 010). Então obrigatoriamente $01$. Após $11|01$, resta 0001111.
• Se pegar $00$, resta 01111.
  • Pode pegar $011$, resta 11 (ok, fecha com $11$). Isso daria $11|01|00|011|11$ que concatena: 11 01 00 011 11 = 11010001111 (confere). Então 3 ∈ L*.

(Observação: a decomposição acima confere exatamente com a cadeia, logo pertence.)

4) 01101000100 Podemos decompor como:

• $011\,|\,01\,|\,00\,|\,01\,|\,00$ Concatenação: 011 01 00 01 00 = 01101000100. Todos os blocos em $L$. Logo, 4 ∈ L*.

5) 11011110111 Uma decomposição possível é:

• $11\,|\,011\,|\,11\,|\,01\,|\,11$ Concatenação: 11 011 11 01 11 = 11011110111. Todos os blocos em $L$. Logo, 5 ∈ L*.

Assim, pertencem a $L^*$ as cadeias 1, 3, 4 e 5.

Alternativa correta: (e).