teoria da computação

apenas a afirmativa I está correta.
b)apenas a afirmativa II está correta.
c)a afirmativa I é falsa e a afirmativa II é verdadeira.
d)a afirmativa I é verdadeira e a afirmativa II é falsa.
e)todas as afirmativas estão corretas.
15.Preencha as lacunas do texto abaixo:
Autômatos Finitos ________________ constituem modelos rudimentares de ______________: computações baseadas em autômatos finitos ____________ realizar tarefas computacionais _________ como é o caso da comparação do número de a´s e de b´s em uma cadeia. Entretanto, autômatos finitos são úteis como partes básicas de computadores e ___________. Por isto, é importante sermos capazes de ________________ o número de estados de um dado autômato finito _________________, isto é, determinar um autômato finito determinístico ______________ que tenha o menor número de estados possíveis.
a)Determinístico – máquinas – podem – complexas – programas – maximizar – não-determinístico – igual.
b)Não-determinístico – computadores – podem – complexas – linguagens – maximizar – determinístico – equivalente.
c)Determinístico – computadores – não podem – simples – algoritmos – minimizar – determinístico – equivalente.
d)Não-determinístico – computadores – não podem – complexas – programas – minimizar – determinístico – igual.
e)Determinístico – máquinas – não podem – simples –éria: Teoria da Computação Professora: Adriana Andrade E-mail: [e-mail]
Aula 08- Revisão para prova
1.Seja a palavra teoria determine:
a)PrefixDada a tabela de transição do autômato finito não determinístico represente o autômato:

9. Considere a linguagem: L=(w|w possui como sufixo a ou bb ou cc} e transcreva sua tabela de transição.

10. Descreva o autômato a partir do traço de execução::
b)Sufixo:
2.Suponha o alfabeto ∑ {a,b} e as palavras v=baa e w=bb, tem-se que:
a)vw=
b)vε=
c)wv=
3. Se abcb é uma palavra sobre o alfabeto {a, b, c}, então defina:
a)*
b)+
c)|abbc|
d)|ε|
4. Derive três sentenças da