Licenciatura: Matemática - Ciências da Computação

Ano Lectivo: 2002/03

Programa:

1. Autómatos finitos.

1. Autómatos finitos deterministas e grafos de transição. Linguagens e autómatos finitos deterministas. A família das linguagens regulares e o conjunto das linguagens aceites pelos autómatos finitos deterministas.
2. Autómatos finitos não deterministas.
3. Equivalência entre autómatos finitos deterministas e não deterministas.

2. Linguagens regulares e gramáticas regulares.

1. Expressões regulares. Expressões regulares e linguagens regulares.
2. Gramáticas regulares. Gramáticas lineares à direita e à esquerda. Equivalência entre linguagens regulares e gramáticas regulares.

3. Propriedades das linguagens regulares.

1. Propriedades de fecho das linguagens regulares.
2. Um lema da Bombagem para linguagens regulares.

1. Gramáticas livres do contexto. Árvores de derivação.
2. Simplificação de gramáticas livres do contexto e formas normais de Chomsky e Greibach.
3. Autómatos pushdown ou de uma pilha.

1. Autómatos pushdown não deterministas.
2. Autómatos pushdown e linguagens livres do contexto.
3. Autómatos pushdown deterministas.

4. Propriedades das linguagens livres do contexto.

1. Um lema da Bombagem para linguagens livres do contexto.
2. Um lema da Bombagem para linguagens lineares.
3. Propriedades de fecho para linguagens livres do contexto.