Exercício 14. Sabemos que a linguagens regulares são fechadas sob as operações abaixo. Mostre quais continuam sendo fechadas para LLC ou não fechadas para LLC.
  • \min (L)=\{w: w está em L, mas nenhum prefixo próprio de w está em L\}
  • \max (L)=\{w: w está em L, mas nenhum x diferente de \varepsilon é tal que wx está em L\}
  • \operatorname{init}(L)=\{w : para algum x, w x está em L\}

Passo 1

O enunciado define, para uma linguagem L\subseteq\Sigma^*, três operações:
\min(L)=\{w\in L\mid\text{nenhum prefixo próprio de }w\text{ está em }L\}óá
\max(L)=\{w\in L\mid\neg\exists x\neq\varepsilon,\;wx\in L\}
\mathrm{init}(L)=\{w\mid\exists x\in\Sigma^*,\;wx\in L\}
Queremos dizer para cada operação se, partindo de uma linguagem livre de contexto L, a linguagem resultante continua sendo livre de contexto (CFL) ou não.

Passo 2

Mostrar que \mathrm{init}(L) é CFL quando L é CFL. Observe que
\mathrm{init}(L) =\{w\mid \exists x,\;wx\in L\}
é exatamente o quociente à esquerda de L por \Sigma^*. Como as CFL são fechadas sob quociente à esquerda por qualquer linguagem regular, e \Sigma^* é regular, segue que \mathrm{init}(L) é CFL.

Passo 3

Expressar \max(L) como diferença de linguagens conhecidas. Note que
L\,\Sigma^+ =\{u v\mid u\in L,\;v\in\Sigma^+,\;v\neq\varepsilon\}
é CFL (concatenação de CFL com regular). E
\max(L) = L \;\setminus\; (L\Sigma^+).
Mas as CFL não são fechadas sob diferença com outra CFL em geral. Logo \max(L) pode deixar de ser CFL.

Passo 4

Fazer o mesmo para \min(L). Temos
\Sigma^+ L =\{u v\mid u\in\Sigma^+,\;v\in L\}
que é CFL (regular \cdot CFL). E
\min(L) = L \;\setminus\; (\Sigma^+ L).
De novo, CFL não são fechadas sob diferença de duas CFL quaisquer, logo \min(L) pode não ser CFL.

Resposta

init (L) continua sendo CFL quando L é CFL.
min (L) e max (L) não são, em geral, CFL.

Exercícios relacionados