Ciencia da computacao

1- Explique e exemplifique a utilização de funções recursivas? Quais são suas vantagens?

Uma função recursiva é uma função que refere a si própria.
Consiste em utilizar a própria função que devemos definir em sua definição.
Em todas as funções recursivas existe:
* Um passo que o resultado é imediatamente conhecido, chamado de básico.
* Um passo que tenta resolver um subproblema do problema inicial, chamado de recursivo.
Exemplo:
int fat (int n) { if (n == 0) return 1; return n*fat (n=1)
}
Principais Vantagens:
* Clareza na interpretação do código.
* Simplicidade e elegância na interpretação.

2- Descreva a teoria gramatical envolvida na Hierarquia de Chomsky. Compare-a ao modelo da Linguagem Formal.

A hierarquia de Chomsky divide as gramaticas formais em classes com crescente poder expressivo, por exemplo, cada classe que sucede pode gerar um conjunto mais amplo de linguagens formais que a classe anterior.
De maneira interessante, Chomsky argumenta que a modelagem para alguns aspectos de linguagem humana precisa de uma gramatica formal mais complexa, que é medida pela hierarquia de Chomsky que modela outro aspecto.
Diferença entre formal e Chomsky:
Enquanto a linguagem formal é suficientemente poderosa para modelar a morfologia da língua inglesa, ela não tem o mesmo poder para modelar a sintaxe da mesma.
A linguagem de Chomsky consegue fazer bem as duas, por isso, tornou-se importante em ciência da computação e na teoria de autômatos.

3- Descreva a diferença entre os 2 principais modelos computacionais (Máquina de Turing e Cálculo Lambda).

A maquina de Turing e o calculo de lambda, apesar de usados em modelos computacionais são 2 coisas diferentes, que foram provadas que unidas foram alcançam um ótimo resultado, no teste Crush-Turing.
A maquina de Turing consiste em um cabeçote de leitura e escrita que manipula dados contidos em uma fita de instruções aonde a posição seguinte não depende da anterior.
O calculo de