Sumários
Inferência indutiva
12 outubro 2018, 10:00 • José Félix Costa
Conceitos de cientista, convergência de cientista para uma hipótese, identificação de conjunto ou de função, identificação de classe de conjuntos ou conjunto de funções.
Exemplos de identificação.
Relation between time and space resources of Turing machines
10 outubro 2018, 16:00 • José Félix Costa
Upper bound on the number of configurations of a space bounded Turing machine.
Decidability of the halting problem of space-bounded Turing machines.
Turing machines and decidability
3 outubro 2018, 16:00 • José Félix Costa
Deterministic Turing machines with k-tapes. Universal Turing machines. Halting problem. Decidability.
Pointers:
Regular expressions
28 setembro 2018, 10:00 • José Félix Costa
Regular expressions.
Use of non-determinism: (1) to synthesise automata from regular expressions and (2) to convert finite automata into regular expressions.
Grammar theory
26 setembro 2018, 16:00 • José Félix Costa
Grammars, context-sensitive grammars, context-free grammars, regular grammars.
Gerative trees.
Equivalence between regular grammars and finite automata.
Pushdown automata.
Equivalence between context-free grammars and pushdown automata.
Chomsky hierarchy.
(Chomsky normal form.) Pumping lemma for context-free languages.
Exemples and exercises.