Gramáticas y Autómatas

Una parte muy importante de la información disponible hoy en día se encuentra disponible en formato textual: páginas web, ficheros de configuración, scripts, programas de ordenador o incluso texto en lenguaje natural. Para que un ordenador pueda utilizar esta información, es necesario que la pueda interpretar según las reglas del lenguaje en que está escrita.

En esta asignatura se presentan técnicas básicas para describir la estructura de un lenguaje, las expresiones regulares y las gramáticas libres de contexto. Estas notaciones son las que se usan, por ejemplo, para describir los lenguajes de programación o describir patrones de texto para hacer búsquedas.

Además, se presentan los mecanismos que utilizan los ordenadores para reconocer si una sentencia está correctamente formada según la estructura de un lenguaje. En concreto se presentan los autómatas finitos y autómatas con pila.

En resumen, esta asignatura proporciona las herramientas básicas para saber tratar información textual con un ordenador.

La asignatura Autómatas y Gramáticas se puede cursar como asignatura optativa o bien como parte del itinerario de Computación.

Dentro de este itinerario, esta asignatura proporciona los conceptos básicos para el análisis de información textual. Estos conocimientos se aplican en Compiladores al análisis de los lenguajes de programación. Además, junto con Inteligencia Artificial y Aprendizaje computacional, la asignatura proporciona las bases utilizadas en las técnicas del procesamiento de lenguaje natural.

Por otro lado, el concepto de autómata como máquinas de estado también se utiliza en muchos ámbitos de la informática, como por ejemplo la descripción de sistemas hardware (Fundamentos de computadores) y software (Ingeniería del software).

Esta asignatura aporta los fundamentos necesarios por cualquier tarea que requiera el tratamiento de información textual. En concreto, estas competencias son imprescindibles para trabajar en la construcción de compiladores e intérpretes de lenguajes de programación o el tratamiento de lenguaje natural (comprensión de textos, reconocimiento de voz, ...).

Por otro lado, los conocimientos de expresiones regulares y gramáticas también facilitan el aprendizaje de nuevos lenguajes de programación, que siempre se describen utilizando estos formalismos.

Por último, el uso de expresiones regulares para describir patrones de busca es muy común en diferentes ámbitos (editores de texto, comandos del sistema operativo para localizar ficheros, buscadores de internet, ...). Hay muchos lenguajes de scripting y procesamiento de documentos de texto como por ejemplo Perl, sed o awk que utilizan de forma intensiva las expresiones regulares para hacer el tratamiento y manipulación de textos.

La asignatura requiere conocimientos básicos del concepto de grafo, que se ha introducido en la asignatura Grafos y Complejidad.

Por otro lado, la asignatura requiere una cierta habilidad con el uso de notación matemática, dado que los lenguajes se describen de manera formal. Por este motivo, se recomienda haber cursado previamente la asignatura de Lógica .

Antes de cursar esta asignatura, es muy recomendable haber cursado previamente las asignaturas siguientes:

• Algebra
• Grafos y Complejidad
• Lógica

Las competencias generales del Grado que se ponen de manifiesto en esta asignatura son:

• Capacidad para utilizar los fundamentos matemáticos, estadísticos y físicos para comprender los sistemas TIC.
• Capacidad para analizar un problema en el nivel de abstracción adecuado a cada situación y aplicar las habilidades y conocimientos adquiridos para resolverlo.

Las competencias específicas de esta asignatura son:

• Saber definir los conceptos de alfabeto, palabra y lenguaje.
• Conocer las operaciones sobre lenguajes y palabras (concatenación, clausuras) y saber utilizarlas para describir lenguajes complejos.
• Saber construir expresiones regulares y gramáticas independientes del contexto para describir un lenguaje dado.
• Saber construir autómatas finitos y autómatas con pila para reconocer las palabras de un lenguaje dado.
• Conocer las relaciones entre autómatas, expresiones regulares y gramáticas y saber pasar de una representación a la otra con destreza.
• Conocer las diferencias entre lenguajes regulares e independientes de contexto y saber clasificar un lenguaje a la familia correspondiente.

La asignatura se estructura en tres módulos: