INF05005/10 - Propriedades de LLC

Seja L1 uma Linguagem Regular e L2 uma LLC, possivelmente NÃO é uma LLC:

• L4 = L1L2

• L5 = L1 U L2

• L6 = ~L1 U L2

Uma LLC L é vazia se:

• Contém somente produções vazias

• Contém produções com substituição de variáveis

• Contém somente símbolos inúteis

• Contém produções alcançáveis que geram terminais

Considerando-se os conjuntos de produções abaixo sobre o alfabeto {a,b} e as variáveis {A,B,C}, qual GLC gera uma linguagem finita?

• A -> BC

  B -> a

  C -> BA

  C -> b

• A -> CC

  B -> AC

  B -> a

  C -> b

  C -> BB

• A -> CB

  B -> CC

  B -> b

  C -> a

• A -> BB

  B -> AC

  B -> a

  C -> b

  C -> AB

Considerando-se as propriedades de LLC, é correto afirmar-se que:

• Somente as LLC seguem o Lema do Bombeamento de LLC

• O complemento de uma LLC finita é uma LLC finita

• A concatenação de duas LLC com uma Linguagem Regular gera uma LLC

Se uma linguagem L é LCC, então, podemos afirmar que:

• Existe um AP com um estado que a aceita por estado final

• Seu complemento é uma Linguagem Regular

• Pode ser reconhecida por um AP determinístico

• É sempre finita