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.
-
está em
, mas nenhum prefixo próprio de
está em
-
está em
, mas nenhum
diferente de
é tal que wx está em
-
: para algum
está em
Passo 1
O enunciado define, para uma linguagem
, três operações:
–
–
–
Queremos dizer para cada operação se, partindo de uma linguagem livre de contexto , a linguagem resultante continua sendo livre de contexto (CFL) ou não.
–
–
–
Queremos dizer para cada operação se, partindo de uma linguagem livre de contexto
Passo 2
Mostrar que
é CFL quando
é CFL. Observe que
é exatamente o quociente à esquerda de
por
. Como as CFL são fechadas sob quociente à esquerda por qualquer linguagem regular, e
é regular, segue que
é CFL.
Passo 3
Expressar
como diferença de linguagens conhecidas. Note que
é CFL (concatenação de CFL com regular). E
Mas as CFL não são fechadas sob diferença com outra CFL em geral. Logo
pode deixar de ser CFL.
Passo 4
Fazer o mesmo para
. Temos
que é CFL (regular
CFL). E
De novo, CFL não são fechadas sob diferença de duas CFL quaisquer, logo
pode não ser CFL.
Resposta
init
continua sendo CFL quando
é CFL.
min e max
não são, em geral, CFL.
min