Educational guide 2024_25 Escola Superior de Enxeñaría Informática

Contidos

Tema	Subtema
Introducción	Peliminares: conxuntos e funcións. Linguaxes formais: Alfabetos, gramáticas Gramáticas formais: Xerarquía de Chomsky, derivacións, árbores de derivación.
Linguaxes Regulares e Autómatas Finitos	Gramáticas Regulares e Expresións Regulares. Autómatas Finitos. Propiedades das Linguaxes Regulares. Gramáticas Regulares
Linguaxes Independentes do Contexto e Autómatas de Pila	Gramáticas Independentes do Contexto. Ambigüidade e Árbores de derivación. Simplificación de Gramáticas Independentes do Contexto e Formas Normais. Autómatas de Pila. Propiedades das Linguaxes Independentes do Contexto. Análise sintáctica.
Linguaxes Recursivos Enumerables e Máquinas de Turing	Máquinas de Turing. Gramáticas sen restriccións. Decidibilidad e complexidade computacional.