Autómatas y gramáticas Código:  75.579    :  6
Consulta de los datos generales   Descripción   La asignatura en el conjunto del plan de estudios   Campos profesionales en el que se proyecta   Conocimientos previos   Información previa a la matrícula   Objetivos y competencias   Contenidos   Consulta de los recursos de aprendizaje de la UOC para la asignatura   Información adicional sobre los recursos de aprendizaje y herramientas de apoyo   Informaciones sobre la evaluación en la UOC   Consulta del modelo de evaluación  
Este es el plan docente de la asignatura para el segundo semestre del curso 2023-2024. Podéis consultar si la asignatura se ofrece este semestre en el espacio del campus Más UOC / La universidad / Planes de estudios). Una vez empiece la docencia, tenéis que consultarlo en el aula. El plan docente puede estar sujeto a cambios.

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.

Amunt

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).

Amunt

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.

Amunt

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 .

Amunt

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

  • Algebra
  • Grafos y Complejidad
  • Lógica

Amunt

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.

Amunt

La asignatura se estructura en tres módulos:

Módulo

Contenidos

Descripción

1. Alfabetos, palabras y lenguajes

1. Elementos básicos: alfabetos, palabras y lenguajes

2. Operaciones sobre palabras

3. Operaciones sobre lenguajes

4. Definición de lenguajes

En este módulo se describen los elementos que forman un lenguaje y las operaciones para manipularlos.

2. Autómatas finitos y lenguajes regulares

1. Autómatas finitos deterministas y lenguajes regulares

2. Autómatas finitos indeterministas

3. Operaciones con autómatas finitos

4. Minimización de autómatas finitos

5. Expresiones regulares

6. El lema de bombeo

Se presenta la clase de lenguajes más simples, los lenguajes regulares. Se proporciona un formalismo para describir estos lenguajes (expresiones regulares) y otro para reconocer las palabras que forman parte de ellos (autómatas con pila).

3. Gramáticas incontextuals y autómatas con pila

1. Conceptos introductorios

2. Árbol de derivación y ambigüedad

3. Verificación de gramáticas

4. Simplificación de una gramática

5. Formas normales

6. Autómatas con pila

7. Propiedades de los lenguajes incontextuals

Se presenta una clase de lenguajes más complejos, denominados independientes del contexto. La estructura de este lenguaje se describir mediante gramáticas y sus palabras se reconocen mediante autómatas con pila.

Amunt

Teoría de autómatas y lenguajes formales I PDF

Amunt

Los módulos didácticos constituyen la parte más importante de los materiales de la asignatura que están accesibles desde el aula en formato digital.

Amunt

En la UOC, la evaluación generalmente es virtual. Se estructura en torno a la evaluación continua, que incluye diferentes actividades o retos; la evaluación final, que se lleva a cabo mediante pruebas o exámenes, y el trabajo final de la titulación.

Las actividades o pruebas de evaluación pueden ser escritas y/o audiovisuales, con preguntas aleatorias, pruebas orales síncronas o asíncronas, etc., de acuerdo con lo que decida cada equipo docente. Los trabajos finales representan el cierre de un proceso formativo que implica la realización de un trabajo original y tutorizado que tiene como objetivo demostrar la adquisición competencial hecha a lo largo del programa.

Para verificar la identidad del estudiante y la autoría de las pruebas de evaluación, la UOC se reserva la potestad de aplicar diferentes sistemas de reconocimiento de la identidad y de detección del plagio. Con este objetivo, la UOC puede llevar a cabo grabación audiovisual o usar métodos o técnicas de supervisión durante la ejecución de cualquier actividad académica.

Asimismo, la UOC puede exigir al estudiante el uso de dispositivos electrónicos (micrófonos, cámaras u otras herramientas) o software específico durante la evaluación. Es responsabilidad del estudiante asegurar que estos dispositivos funcionan correctamente.

El proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de las actividades académicas. La web sobre integridad académica y plagio de la UOC contiene información al respecto.

La falta de autenticidad en la autoría o de originalidad de las pruebas de evaluación; la copia o el plagio; la suplantación de identidad; la aceptación o la obtención de cualquier actividad académica a cambio o no de una contraprestación; la colaboración, el encubrimiento o el favorecimiento de la copia, o el uso de material, software o dispositivos no autorizados en el plan docente o el enunciado de la actividad académica, incluida la inteligencia artificial y la traducción automática, entre otras, son conductas irregulares en la evaluación que pueden tener consecuencias académicas y disciplinarias graves.

Estas conductas irregulares pueden conllevar el suspenso (D/0) en las actividades evaluables definidas en el plan docente -incluidas las pruebas finales- o en la calificación final de la asignatura, ya sea porque se han utilizado materiales, software o dispositivos no autorizados durante las pruebas (como el uso de inteligencia artificial no permitida, redes sociales o buscadores de información en internet), porque se han copiado fragmentos de texto de una fuente externa (internet, apuntes, libros, artículos, trabajos o pruebas de otros estudiantes, etc.) sin la citación correspondiente, por la compraventa de actividades académicas, o porque se ha llevado a cabo cualquier otra conducta irregular.

Asimismo, y de acuerdo con la normativa académica, las conductas irregulares en la evaluación también pueden dar lugar a la incoación de un procedimiento disciplinario y a la aplicación, si procede, de la sanción que corresponda, de conformidad con lo establecido en la normativa de convivencia de la UOC.

En el marco del proceso de evaluación, la UOC se reserva la potestad de:

  • Solicitar al estudiante que acredite su identidad según lo establecido en la normativa académica.
  • Solicitar al estudiante que acredite la autoría de su trabajo a lo largo de todo el proceso de evaluación, tanto en la evaluación continua como en la evaluación final, a través de una entrevista oral síncrona, que puede ser objeto de grabación audiovisual, o por los medios establecidos por la UOC. Estos medios tienen el objetivo de verificar los conocimientos y las competencias que garanticen la identidad del estudiante. Si no es posible garantizar que el estudiante es el autor de la prueba, esta puede ser calificada con una D, en el caso de la evaluación continua, o con un suspenso, en el caso de la evaluación final.

Inteligencia artificial en el marco de la evaluación

La UOC reconoce el valor y el potencial de la inteligencia artificial (IA) en el ámbito educativo y, a su vez, pone de manifiesto los riesgos que supone si no se utiliza de forma ética, crítica y responsable. En este sentido, en cada actividad de evaluación se informará al estudiantado sobre las herramientas y los recursos de IA que se pueden utilizar y en qué condiciones. Por su parte, el estudiantado se compromete a seguir las indicaciones de la UOC a la hora de realizar las actividades de evaluación y de citar las herramientas utilizadas y, concretamente, a identificar los textos o imágenes generados por sistemas de IA, los cuales no podrá presentar como si fueran propios.

Respecto a usar o no la IA para resolver una actividad, el enunciado de las actividades de evaluación indica las limitaciones en el uso de estas herramientas. Debe tenerse en cuenta que usarlas de manera inadecuada, como por ejemplo en actividades en las que no están permitidas o no citarlas en las actividades en las que sí lo están, puede considerarse una conducta irregular en la evaluación. En caso de duda, se recomienda que, antes entregar la actividad, se haga llegar una consulta al profesorado colaborador del aula.

Amunt

Puedes superar la asignatura a través de dos vías:

  1. Siguiendo la evaluación continua (EC). Puedes superar la asignatura directamente aprobando la EC. En este caso, la nota final de la asignatura se corresponderá con la nota final de la evaluación continua.
  2. Haciendo un examen. La nota final se calculará de acuerdo con lo siguiente:
    • Si no te has presentado a la evaluación continua, la nota final será la calificación numérica obtenida en el examen.
    • Si has seguido la evaluación continua y tienes una nota distinta a un No presentado, la calificación final será el cálculo más favorable entre la nota numérica del examen y la ponderación de la nota de la evaluación continua con la nota del examen, según lo establecido en el plan docente. Para aplicar este cálculo, es necesario obtener una nota mínima de 4 en el examen (si es inferior, la nota final de la asignatura será la calificación del examen).
    • Si no te presentas al examen, la calificación final será un No presentado.

 

Amunt