Ementa:
Palavras e linguagens. Gramáticas regulares e autômatos finitos. Não determinismo e generalizações. Minimização de estados. Expressões regulares. Teorema da iteração para linguagens regulares. Gramáticas livres de contexto e autômatos com pilha. Determinismo e ambiguidade. Teorema da iteração para linguagens livres de contexto. Gramáticas sensíveis ao contexto e autômatos lineares. Gramáticas e máquinas de Turing. Generalizações e restrições. Determinismo e algoritmos. Recursão e enumeração. Decidibilidade. O problema de Post. Operações com linguagens. Transdutores e operações fechadas.
Bibliografia: Hopcroft, J. e Ullman, J., þIntroduction to Automata Theory, Languages, and ComputationÞ, Addison Wesley, 1979. Sipser, M þIntroduction to the Theory of ComputationÞ, PWS Pub. Co., 1997. Kelley, D. þAutomata and Formal LanguagesÞ, Prentice Hall, 1995. Floyd, R. e Beigel, R. þThe Language of Machines: An Introduction to Computability and Formal LanguagesÞ, W. H. Freeman Co., 1994.
Ano de Catálogo: 2018
Créditos: 4
Número mínimo de alunos: 5
Número de alunos matriculados: 4
Tipo Oferecimento: Regular
Local Oferecimento:
Horários/Salas:
Docentes:
Reservas:
| Hora | Segunda | Terça | Quarta | Quinta | Sexta | Sábado |
|---|---|---|---|---|---|---|
| 07:00 | ||||||
| 08:00 | ||||||
| 09:00 | ||||||
| 10:00 | A - CB10 | A - CB10 | ||||
| 11:00 | A - CB10 | A - CB10 | ||||
| 12:00 | ||||||
| 13:00 | ||||||
| 14:00 | ||||||
| 15:00 | ||||||
| 16:00 | ||||||
| 17:00 | ||||||
| 18:00 | ||||||
| 19:00 | ||||||
| 20:00 | ||||||
| 21:00 | ||||||
| 22:00 | ||||||
| 23:00 |