Question

Considere a linguagem L = { wcw^R / w ∈ {a,b} * } . Assinale a alternativa correta.

a. Um AP determinístico P faz o seguinte: empilha cada símbolo lido da fita e após ler c passa a desempilhar conforme leia o mesmo símbolo que é topo da pilha. Portanto P aceita L .
b. L = { wcw^R / w ∈ {a,b} * } não é aceita por APD. [ Incorreto ]
c. Sem o caractere c no centro da cadeia, a linguagem ainda poderia ser aceita por APD.
d. O complemento de L não é livre de contexto.
e. L estendida para incluir todos os caracteres da língua portuguesa, não é uma linguagem livre de contexto, pois o APND não lida com muitos símbolos.

Answer 1

a. Um AP determinístico P faz o seguinte: empilha cada símbolo lido da fita e após ler c passa a desempilhar conforme leia o mesmo símbolo que é topo da pilha. Portanto P aceita L

Answer 2

Um AP determinístico P faz o seguinte: empilha cada símbolo lido da fita e após ler c passa a desempilhar conforme leia o mesmo símbolo que é topo da pilha. Portanto P aceita L