Programa

Teoria da Computação

Licenciatura (5 anos) em Engenharia Informática e de Computadores - Taguspark

Programa

Autómatos finitos deterministas. Propriedades de fecho de linguagens regulares. Equivalência e minimização de autómatos finitos deterministas. Lema da bombagem para linguagens regulares. Autómatos finitos não deterministas. Equivalência de autómatos finitos deterministas e não deterministas relativamente às linguagens reconhecidas. Gramática, gramática livre de contexto e gramática regular. Expressões regulares. Raciocínio sobre expressões regulares. Conversão entre as diferentes representações de linguagens regulares: da gramática regular para a expressão regular e da expressão regular para a gramática regular; da expressão regular para o autómato finito não determinista com movimentos épsilon; do autómato finito determinista para a gramática regular; da gramática regular para o autómato finito não determinista. Máquina URM. Funções computáveis e predicados decidíveis. A classe das funções parciais recursivas: definição indutiva (estudo detalhado da composição, recursão e minimização). Teorema de Kleene: identidade das classes das funções computáveis pela máquina URM e das funções parciais recursivas. Gödelização de programas URM. Existência de funções não computáveis: diagonalização. O teorema s-m-n e o teorema de Rice. Funções universais e programa universal. Problemas clássicos da computabilidade e da decidibilidade (problema da paragem inter alia) e aplicações.