Questões Revisão para a primeira prova Monitoria 2014.2

Prévia do material em texto

Questões - Revisão para 
a 1ª prova
Monitoria de Informática Teórica
Natalia Cometti (npvc)
1º EE - 2013.2
Prove que toda linguagem que pode ser descrita por uma 
expressão regular é regular.
1º EE - 2013.2
Prove que toda linguagem que pode ser descrita por uma 
expressão regular é livre-do-contexto.
1º EE - 2013.2
1º EE 2014.1
Seja L = {w ∈ {a,b}* | w não termina com ab}. Dê:
(i) Uma expressão regular que descreve/gera L.
(ii) Um autômato finito que reconhece L.
1º EE 2014.1
Defina um autômato finito (possivelmente não-
determinístico) que reconheça a linguagem L = {w ∈ {0,1}* 
| w contém pelo menos uma ocorrência de 0010, 111 ou 
01010}.
1º EE 2014.1
A diferença simétrica de duas linguagens L1 e L2 é o 
conjunto de cadeias que pertence a exatamente uma das 
duas linguagens. Mostre que a classe das linguagens 
regulares é fechada sob a operação diferença simétrica.
1º EE 2014.1
A derivada de uma linguagem L ⊆ ∑* com respeito a um símbolo a ∈ ∑ é 
definida da seguinte forma:
∂L = {w ∈ ∑* | aw ∈ L}
A derivada contém todas as cadeias que podem ser obtidas tomando uma 
cadeia em L que começa com um a e remove-se o a. (Cadeias em L que não 
começam com um a são eliminadas completamente.) Por exemplo, se L = {00, 
110, 011, 001, 0000, 11111}, então temos que ∂L = {0, 11, 01, 000}. Mostre 
que
se L for regular, então ∂L é regular para todo a ∈ ∑. (Dica: Considere um AFD
para a linguagem L e modifique-o para um AFD para a linguagem ∂L.)
∂a
∂a
∂a
∂a
1º EE 2013.2 e 2014.1
Mostre que a classe de linguagens livres-do-contexto é 
fechada sob as operações regulares: união, concatenação 
e estrela.
1º EE 2013.2
1º EE 2014.1
Use o lema do bombeamento para mostrar que a seguintes 
linguagem não é livre-do-contexto:
L = {w#t | w é uma subcadeia de t, onde w, t ∈ {a,b}*}
1º EE de 2013.2 e 2014.1
Descreva os passos para conversão de um autômato com 
pilha (AP) em uma gramática-livre-do-contexto (GLC), e os 
passos para conversão de uma GLC em um AP.