Aula9

28 Abril 2026, 10:00 • Isabel Gama Nunes

Examples of decidable languages.

Algorithms and Turing machines.

Operations with decidable languages.

Closure of the class of decidable languages and of recognizable languages under the union operation.

Universal Turing machines.

(Sipser's book, Sections 3.3 and 4.1)

---

Aula8

21 Abril 2026, 10:00 • Isabel Gama Nunes

Exercises on push-down automata.

Turing machines. Three formats for describing Turing machines: formal, implementation and high-level. Turing-decidable and Turing-recognizable languages.

 (Sipser's book, Section 3.1)

---

Aula7

14 Abril 2026, 10:00 • Isabel Gama Nunes

Some exercises on context-free grammars

Pushdown automata (Sipser's book section 2.2.)

Second individual evaluation test.

---

Aula6

31 Março 2026, 10:00 • Isabel Gama Nunes

Non-regular languages.

Pumping lemma for regular languages. (Sipser's book, Section 1.4)

Context-free languages and grammars (Sipser's book, Section 2.1)

Some exercises on context-free grammars

---

Aula5

24 Março 2026, 10:00 • Isabel Gama Nunes

Regular expressions.  (Sipser's book, Chapter 1.3)
Regular expressions and finite automata are equivalent in their descriptive power.

---