Sumários

Pushdown automata

7 outubro 2016, 11:00 • José Félix Costa

Chomsky normal form. Pumping lemma for context-free languages.

Pushdown automata.

Grammar theory

30 setembro 2016, 11:00 • José Félix Costa

Grammars, context-sensitive grammars, context-free grammars, regular grammars. Gerative trees.

Equivalence between regular grammars and finite automata.

Chomsky hierarchy.

Regular expressions

28 setembro 2016, 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.

Non-determinism

23 setembro 2016, 11:00 • José Félix Costa

Closure of the class of regular languages under complement, union, and intersection.
Non-determinism.

Simulador: http://www.cburch.com/proj/autosim/index.html

Finite automata

21 setembro 2016, 10:00 • José Félix Costa

Concept of deterministic finite automaton. Regular sets. Examples.

Pumping Lemmas.