Teoria da Computação - Lista 1a unidade 2018 1

Prévia do material em texto

Universidade Federal Rural do Semi-árido – UFERSA 
Departamento de Ciências Exatas e Tecnologia da Informação
Bacharelado em Sistemas e Computação
Licenciatura em Computação e Informática
Disciplina: Teoria da Computação 
Professor: Samuel Oliveira de Azevedo
Lista de Revisão da 1ª Unidade
1. Dado um alfabeto Σ = {a,...,z,0,...,9}, calcule:
a. |λ|
b. |13|
c. |ufersa|
d. |2014|
e. |ufersa2014|
2. Dado Σ = {a,b} , L1 ⊆Σ*, L2 ⊆ Σ*, L1={a,b}* e L2= {b}*, calcule:
3. Usando ainda Σ, L1 e L2 da questão anterior, prove:
http://pt.wiktionary.org/w/index.php?title=%E2%8A%86&action=edit&redlink=1
http://pt.wiktionary.org/w/index.php?title=%E2%8A%86&action=edit&redlink=1
4. Explique o que é um Autômato Finito Determinístico, descreva cada um de seus
elementos e explique porque ele é finito e porque é determinístico.
5. Explique o que é um Autômato Finito Não Determinístico, descreva cada um de
seus elementos e explique porque ele é finito e porque é não determinístico.
6. Dado w1 = 0001, w2 = 010011, w3 = 0000110, quais são reconhecidas pelo 
autômato abaixo?
7. Descreva (Σ, Q, q0, F, δ) do AFD da questão anterior, e responda:
a. Qual é o estado inicial?
b. Qual é o conjunto de estados de aceitação?
c. Por qual sequência de estados a máquina passa para a entrada 
01110110.
d. A máquina aceita a cadeia 110?
e. A máquina aceita a cadeia vazia?
8. Dado o alfabeto Σ = {0,1}, estado inicial q1, estados finais {q3,q4}, e função de 
transição δ1 a seguir, ilustre o gráfico deste AFD.
δ1 0 1
q1 q1 q2
q2 q3 q4
q3 q1 q2
q4 q3 q4
9. Que linguagem o AFD acima reconhece?
10. Para Σ = {a,b}, construa um AFD para a linguagem L = {ab}* - {λ}.
11. Para um alfabeto Σ = {a,b}, escreva um AFN que descreva:
a. Qualquer palavra com número par de a.
b. Todas as cadeias que terminem em ab.
c. Todas as cadeias que contenham a palavra abba.
d. {w / w tem pelo menos três a}
e. {w / w tem dois 2 a e pelo menos 2 b}
f. {w / tem um número ímpar de a e termina com um b}
g. {w / |w| é par}
h. {w / |w| é impar}
i. A cadeia começa com a e termina com b.
12. Faça um autômato para reconhecer somente a sequência 10110. O autômato 
que você fez é um AFD ou AFN? Porquê?
13. Construa um AFN que aceite a linguagem {ab,abc}*
14. Descreva o AFN abaixo em função de (Σ, Q, q0, F, δ).