Licenciatura: Matemática - Ciências da Computação
Ano
Lectivo:
2003/04
Programa:
I.
Conceitos básicos sobre linguagens e gramáticas.
1.
Gramáticas geradoras. Exemplos.
II.
Autómatos finitos e linguagens regulares.
1.
Autómatos finitos.
1.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.
1.2.
Autómatos finitos não deterministas.
1.3. Equivalência entre autómatos finitos
deterministas e não deterministas.
2.
Linguagens regulares e gramáticas regulares.
2.1. Expressões regulares.
Expressões regulares e linguagens regulares.
2.2.
Gramáticas regulares. Gramáticas
lineares à direita e à esquerda. Equivalência
entre linguagens regulares e gramáticas regulares.
3.
Propriedades das linguagens regulares.
3.1. Propriedades de fecho das
linguagens regulares.
3.2. Um lema da Bombagem para linguagens regulares.
III.
Linguagens livres do contexto e
autómatos pushdown ou de uma pilha.
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.
3.1. Autómatos pushdown
não deterministas.
3.2. Autómatos pushdown e
linguagens livres do contexto.
3.3. Autómatos pushdown
deterministas.
4.
Propriedades das linguagens livres do contexto.
4.1. Um lema da Bombagem para linguagens livres do contexto.
4.2. Um lema da Bombagem para linguagens lineares.
4.3. Propriedades de fecho para
linguagens livres do contexto.