Prova1 v2

Prévia do material em texto

1a Avaliação de Teoria da Computação – 31/07/2017
Aluno: __________________________________________________________
Don’t Panic!
(2,0) 1. Assinale as afirmativas a seguir como verdadeira (V) ou falsa (F).
a) Toda linguagem regular é também uma linguagem livre de contexto.
b) Para todo autômato finito existe um autômato com pilha equivalente.
c) Linguagens livre de contexto são fechadas sob a operação de interseção.
d) NFAs são capazes de reconhecer mais linguagens que DFAs.
e) {ak bk ck | k≥0} é uma linguagem livre de contexto.
(2,0) 2. Complete as afirmações seguintes.
a) {ak bk | k≥0} é uma linguagem ____________________.
b) Linguagens livres de contexto são fechadas sob as operações ____________________.
c) Uma gramática que reconhece a união das linguagens geradas por duas gramáticas livre de
contexto cujas variáveis iniciais são S1 e S2, tem como regra inicial: S→_______________.
d) Uma gramática que reconhece a concatenação das linguagens geradas por duas gramáticas livre
de contexto cujas variáveis iniciais são S1 e S2, tem como regra inicial: S→_______________.
e) Uma gramática que reconhece a estrela de uma linguagem gerada por uma gramática livre de
contexto cuja variável inicial é S1 tem como regra inicial: S→_______________.
(3,0) 3. Dê o autômato finito não determinístico (NFA) e a gramática livre de contexto (CFG)
equivalentes à seguinte expressão regular: a (abb)* ∪ b
(3,0) 4. Um sistema de segurança (não muito seguro) armazena até 4 usuários, representados por
dois dígitos binários, cada usuário tem uma senha binária de 3 dígitos. O sistema funciona da
seguinte forma:
• Ao digitar o número do usuário, qualquer quantidade de dígitos pode ser entrada, mas
apenas os dois últimos são considerados (i.e. 01001100100111 corresponde ao usuário 11).
• O símbolo # indica o fim da entrada. Se o número de usuário é válido, dá-se início à
entrada da senha.
• Ao digitar a senha, qualquer quantidade de dígitos pode ser entrada, mas apenas os três
primeiros são considerados (i.e. 01001100100111 corresponde à senha 010).
• O símbolo # indica o fim da entrada. Se a senha está correta, o acesso é permitido, e o
sistema passa para um estado de aceitação, de onde não sai mais.
• Toda entrada inválida trava o sistema (vai para um estado de onde não pode mais sair).
Considere que apenas o usuário 01, cuja senha é 101, está cadastrado.
a) Desenhe um autômato que representa o sistema.
b) Escreva a expressão regular ou gramática livre de contexto que representa o sistema.