Teoria da Computacao

Teoria da Computação e Linguagens Formais

SCE0185Teoria da Computação e Linguagens Formais

João Luís Garcia Rosa1

1Instituto de Ciências Matemáticas e de ComputaçãoUniversidade de São Paulo - São Carlos

[email protected]

2008

João Luís Garcia Rosa, 2008 SCE0185 - Teoria da Computação e Linguagens Formais

[email protected]

Teoria da Computação e Linguagens Formais

Sumário

1 Teoria da Computação e Linguagens FormaisA disciplina SCE0185Objetivos e ProgramaAvaliação


Teoria da Computação e Linguagens FormaisA disciplina SCE0185Objetivos e ProgramaAvaliação

Sumário




A disciplina

A disciplina é composta de três partes centrais da Teoriada Computação que têm o objetivo de tentar responderquais são as capacidades e as limitações doscomputadores:

1 Teoria das Linguagens Formais e dos Autômatos2 Teoria da Computabilidade3 Teoria da Complexidade

A primeira parte trata das definições e propriedades demodelos matemáticos de computação que têm um papelfundamental em várias áreas da Computação como oprocessamento de textos, compiladores, definição delinguagens de programação, dentre outras.Além desse lado prático, do ponto de vista teórico, para sedefinir o que é ou não computável é necessário utilizar ummodelo matemático que represente o que se entende porcomputação.



A disciplina

A segunda parte do curso é centralizada na Tese deChurch-Turing e nas evidências dela.Church usou um sistema chamado cálculo-λ para definiralgoritmo e Turing fez o mesmo com o uso da Máquina deTuring (MT).As duas definições foram mostradas serem equivalentes ea conexão entre a noção informal de algoritmo (solúvelefetivamente) e a definição precisa por uma MT foichamada Tese de Church-Turing: se um problemaalgorítmico não pode ser resolvido por uma máquina deTuring, então não existe nenhuma solução computávelpara ele.



A disciplina

Vários outros modelos de computação (por exemplo, asfunções recursivas de Kleene, linguagens formais, RAMs,algoritmos de Markov, linguagens de programação, amáquina de Post) foram propostos e provados terem poderequivalente a Maquina de Turing.Assim, estudando qualquer um destes modelos, porexemplo um modelo simples como a Máquina de Turing, épossível aprender sobre as limitações teóricas de todos oscomputadores.



A disciplina

Nem todos os problemas algorítmicos, que podem serresolvidos em princípio, podem ser resolvidos na prática:os recursos computacionais requeridos (tempo ou espaço)podem ser proibitivos.Esta observação motiva o estudo da complexidadecomputacional que será tratada na terceira parte do curso.A meta principal da teoria da complexidade é aclassificação de problemas de acordo com a dificuldadecomputacional.A meta da teoria da computabilidade em solúveis,parcialmente solúveis e não solúveis e se forem problemasde decisão em problemas decidíveis, parcialmentedecidíveis e indecidíveis.



Programa de Aperfeiçoamento de Ensino

PAEPaulo Henrique Ribeiro Gabriele-mail: [email protected]


[email protected]


Sumário




Objetivos

Dar ao aluno noção formal de algoritmo, computabilidadee do problema de decisão, de modo a deixá-lo conscientedas limitações da ciência da computação.Aparelhá-lo com as ferramentas de modo a habilitá-lo amelhor enfrentar a solução de problemas com o auxílio docomputador.Dar subsídios para o aluno poder definir linguagens deprogramação, isto é, sua sintaxe e semântica, através doestudo das gramáticas formais.



Programa

1 Linguagens Regulares e Autômatos Finitos1 A Primeira Linguagem2 Gramáticas e Linguagens3 Propriedades de Fechamento4 Linguagens Regulares e de Estados Finitos5 Autômatos de Estados Finitos6 Autômatos Finitos com Arcos-λ7 Minimização de um Autômato Finito8 Autômatos Finitos com Saída



Programa

2 Linguagens Livres de Contexto e Autômatos de Pilha1 Linguagens Livres de Contexto2 Programas, Linguagens e Parsing3 Gramáticas Livres de Contexto e a Língua Natural4 Formas Normais para Gramáticas Livres de Contexto5 Autômatos de Pilha6 O Teorema da Equivalência



Programa

3 Linguagens Sensíveis ao Contexto e Autômatos LimitadosLinearmente

1 Gramáticas e Linguagens Sensíveis ao Contexto2 Máquinas de Turing3 Autômatos Limitados Linearmente

4 Linguagens Recursivamente Enumeráveis e Máquinas deTuring

1 Definição de Gramáticas Irrestritas2 Das Gramáticas para as Máquinas de Turing3 Das Máquinas de Turing para as Gramáticas4 A Máquina de Turing Universal5 Máquinas de Turing Não Determinísticas6 Técnicas para Construção de Máquinas de Turing



Programa

5 Teoria da Computação1 Poder das Máquinas de Turing2 Tese de Church-Turing3 O Problema da Parada e a Indecidibilidade4 Teoria da Complexidade

Aulas:Turma 1-A: Segundas/Quintas: 8h10-9h50 - sala 5104Turma 2-B: Terças/Sextas: 10h10-11h50 - sala 5103



Sumário




Avaliação

3 provas:P1 = 18/09 (turma 1-A); 19/09 (turma 2-B)P2 = 06/11 (turma 1-A); 07/11 (turma 2-B)P3 = 11/12 (turma 1-A); 12/12 (turma 2-B)

Exercícios e Trabalhos Práticos em grupo, comimplementação T1, T2 e T3:

Apresentação do Trabalho T1: 22 a 26/09.Apresentação do Trabalho T2: 20 a 25/11.Apresentação do Trabalho T3: durante o semestre.

MP = Média Ponderada das Provas:MP = P1 ∗ 0, 4 + P2 ∗ 0, 3 + P3 ∗ 0, 3

MT = Média Aritmética dos TrabalhosMF = Média Final:

Se MP ≥ 5, 0 e MT ≥ 5, 0 então MF = (7*MP + 3*MT)/10Se MP < 5, 0 ou MT < 5, 0 então MF = menor valor entreMP e MT



Avaliação: Recuperação

Norma de Recuperação1 prova de recuperação PRRealização: Até a primeira semana de aulas do semestreposterior.Critério de Aprovação:

Média = MF + (PR/2, 5), se PR ≥ 7, 5; ouMédia = Max{MF , PR}, se PR < 5, 0; ouMédia = 5, 0, se 5, 0 ≤ PR < 7, 5.



Agradecimento

Agradeço à Profa. Dra. Sandra Aluisio pelo material, apoio eorientação.


Apêndice Bibliografia

Bibliografia I

[1] Hopcroft, J. E., Ullman, J. D.Formal Languages and Their Relation to Automata.Addison-Wesley Publishing Company, 1969.

[2] Hopcroft, J. E., Ullman, J. D. e Motwani, R.Introdução à Teoria de Autômatos, Linguagens eComputação.Tradução da segunda edição americana. Editora Campus,2003.

JFLAP Version 6.0.Ferramenta para Diagrama de Estados.www.jflap.org.


www.jflap.org


Bibliografia II

[3] Mealy, G. H.A method for synthesizing sequential circuits.Bell Systems Technical Journal 34:5, pp. 1045-1079, 1955.

[4] Menezes, P. B.Linguagens Formais e Autômatos.Série Livros Didáticos. 4a. Edição. Instituto de Informáticada UFRGS. Editora Sagra Luzzatto, 1997.

[5] Moll, R. N., Arbib, M. A., and Kfoury, A. J.An Introduction to Formal Language Theory.Springer-Verlag, 1988.



Bibliografia III

[6] Moore, E. F.Gedanken experiments on sequential machines.in C. E. Shannon and J. McCarthy (Eds.), AutomataStudies, Princeton University Press, pp. 129-153, 1956.

[7] Rosa, J. L. G.Linguagens Formais e Autômatos.Notas de Aula. Engenharia de Computação. PontifíciaUniversidade Católica de Campinas, 2007.

[8] Sipser, M.Introduction to the Theory of Computation.Second Edition, Thomson, 2006.



Bibliografia IV

[9] Taylor, R. G. and Taylor, S.Models of Computation and Formal Languages.Oxford University Press, 1997. Deus Ex Machina:www.ics.uci.edu/~savoiu/dem/


www.ics.uci.edu/~savoiu/dem/

Technology

Teoria da Computacao