Class Nine

29 Abril 2025, 10:00 • Isabel Gama Nunes

Turing-decidable and Turing-recognizable languages.

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

Examples of decidable languages.

Algorithms and Turing machines.

(Sipser's book, Sections 3.1, 3.3 and 4.1)

---

Class Eight

15 Abril 2025, 10:00 • Isabel Gama Nunes

Exercises on push-down automata

Turing machines (Sipser's book, Section 3.1)

---

Class Seven

8 Abril 2025, 10:00 • Isabel Gama Nunes

---

Class Six

1 Abril 2025, 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

---

Class Five

25 Março 2025, 10:00 • Isabel Gama Nunes

Union, Concatenation and Star operations are closed on the class of regular languages.
Regular expressions.  (Sipser's book, Chapter 1.3)
Regular expressions and finite automata are equivalent in their descriptive power.

---