Fundamentos de Informática: Un Recorrido por Conceptos Clave

Clase 1: Introducción a Python y Conceptos Básicos

• Características generales de Python: Es un lenguaje interpretado, no requiere compilación. Admite múltiples paradigmas: orientado a objetos, imperativo y funcional. Es multiplataforma, por lo que puede ejecutarse en distintos sistemas operativos (Linux, Windows, etc.). Posee tipado dinámico, lo que implica que no es necesario declarar el tipo de una variable.
• Manejo de variables: Las variables no se declaran previamente. Se crean automáticamente al asignarles un valor. Se distingue entre mayúsculas y minúsculas (es sensible a mayúsculas y minúsculas). Las variables pueden cambiar de tipo dinámicamente, según lo que se les asigne.
• Tipos de datos: Se describen los tipos primitivos:
  • Numéricos: enteros y reales (con precisión de coma flotante).
  • Booleanos: valores de verdad (True y False).
  • Cadenas de caracteres: representan textos.
  Además, se explican sus operaciones válidas: aritméticas, relacionales y lógicas.
• Conversión de tipos: Se explica cómo convertir datos entre distintos tipos (por ejemplo, de texto a número) y por qué esto es necesario en determinadas situaciones.
• Operadores:
  • Aritméticos: para realizar cuentas matemáticas básicas y avanzadas.
  • Relacionales: para comparar valores.
  • Lógicos: para combinar condiciones.
• Manejo de cadenas: Se presenta la estructura de las cadenas de caracteres, funciones para manipularlas y cómo realizar operaciones básicas como unir, repetir, cambiar el caso o comprobar ciertas propiedades.
• Entrada y salida: Se introducen las funciones fundamentales para interactuar con el usuario a través de la consola, permitiendo ingresar datos y mostrar resultados.
• Control de flujo: Si bien solo se menciona, se anticipa el uso de estructuras como if, while y for, que se desarrollarán más adelante.

Clase 2: Tipos Abstractos de Datos (TAD)

• Abstracción de datos: Se define como la capacidad de concentrarse en los aspectos esenciales de un objeto, dejando de lado los detalles irrelevantes. Esta capacidad permite modelar problemas reales de forma clara, separando el «qué hace» del «cómo lo hace».
• Definición de TAD: Un Tipo Abstracto de Datos (TAD) es una colección de datos acompañada de un conjunto de operaciones válidas para manipularlos. La idea es ocultar al usuario la representación interna y la implementación de las operaciones. El usuario solo conoce la interfaz, es decir, cómo utilizarlo.
• Comparación con tipos estándar: Se establece una analogía entre los tipos de datos estándar (como enteros o booleanos) y los definidos por el usuario (como Alumno o Curso). Ambos tienen estructura y operaciones asociadas, pero en los TAD el programador define cómo están representados internamente y puede modificar su implementación.
• Componentes de un TAD:
  • Interfaz pública (especificación): define para qué sirve el TAD, qué operaciones existen y cómo se llaman. El usuario solo interactúa con esta parte.
  • Implementación privada: incluye la estructura interna de datos y el código de las operaciones, conocido solo por el diseñador del TAD.
• Características clave:
  • Encapsulamiento: se agrupan los datos y las operaciones que los manipulan en una misma unidad.
  • Ocultamiento de información: el usuario no tiene acceso directo a los datos internos, solo puede usar las operaciones definidas.
  • Generalización: posibilidad de crear estructuras reutilizables y adaptables a distintos contextos.
• Proceso de diseño de un TAD:
  • Especificación: se define el nombre del TAD, su utilidad y sus operaciones.
  • Diseño de la estructura interna: se elige el tipo de datos más adecuado para representar la información.
  • Implementación: se codifican las operaciones según lo especificado, usando el lenguaje elegido (por ejemplo, Python).

Clase 3: TAD Compuesto

• Definición de TAD Compuesto: Un TAD compuesto es aquel cuya estructura interna está formada por uno o más TAD preexistentes. Esta composición permite representar entidades más complejas del mundo real, como por ejemplo un curso que contiene muchos alumnos.
• Principios del diseño: El proceso sigue los mismos tres pasos del diseño de un TAD:
  • Especificación: qué representa y qué operaciones ofrece.
  • Diseño de la estructura interna: selección de estructuras de datos (como listas, tuplas, etc.) para almacenar múltiples elementos.
  • Implementación: codificación de las operaciones utilizando los TAD internos ya definidos.
• Ejemplo estructural (sin detallar el código): Se plantea cómo modelar un TAD que representa un curso. Este nuevo TAD reutiliza el TAD Alumno y define operaciones nuevas acordes al concepto de curso: agregar alumno, eliminarlo, recuperar uno por posición, consultar si pertenece, contar la cantidad, etc.
• Importancia del enfoque modular:
  • Permite reutilizar código previamente implementado (los TAD internos).
  • Se mejora la claridad del diseño y la escalabilidad del sistema.
  • Se puede modificar internamente un TAD sin afectar a los programas que lo utilizan, siempre que se mantenga su interfaz pública.
• Aplicación práctica: Se muestra cómo implementar un TAD compuesto usando listas en Python, importando los módulos correspondientes para usar los TAD internos y programar las operaciones nuevas del TAD compuesto.
• Implementación en Python: El TAD compuesto se implementa como un módulo separado, siguiendo el principio de encapsulamiento. Luego puede ser utilizado en otros programas, permitiendo construir sistemas más complejos sobre una base sólida.

Clase 4: Autómatas y Lenguajes Formales

• Lenguaje formal y su estructura: Un lenguaje formal se define sobre un alfabeto (conjunto finito de símbolos). Toda palabra del lenguaje es una combinación de estos símbolos. La validez de estas palabras se rige por reglas sintácticas y su significado por reglas semánticas.
• Conceptos clave:
  • Alfabeto (Σ): conjunto de símbolos (ej. letras, dígitos).
  • Palabra: secuencia finita de símbolos del alfabeto.
  • Palabra vacía (ε): palabra sin símbolos.
  • Concatenación: operación para formar palabras nuevas.
  • Σ*: conjunto de todas las palabras posibles sobre un alfabeto (lenguaje universal).
• Lenguaje (L): Es un subconjunto de Σ*. Puede estar formado por ninguna, una o infinitas palabras. Puede definirse explícitamente o mediante reglas, autómatas o gramáticas.
• Operaciones sobre lenguajes: Unión, intersección, concatenación. Estas operaciones permiten construir lenguajes nuevos a partir de otros.
• Clasificación de lenguajes – Jerarquía de Chomsky: Los lenguajes se clasifican según la complejidad de sus reglas:
  • Regulares (Tipo 3): los más simples, permiten expresar repeticiones simples.
  • Libres de contexto (Tipo 2): utilizados en lenguajes de programación.
  • Sensibles al contexto (Tipo 1): dependen del contexto de los símbolos.
  • Recursivamente enumerables (Tipo 0): sin restricciones, como los lenguajes naturales.
• Máquinas de estado: Modelo abstracto para representar el comportamiento de un sistema:
  • Estados: representan situaciones persistentes.
  • Transiciones: indican los cambios de estado frente a estímulos (eventos).
  Son útiles para representar comportamientos deterministas y secuenciales.
• Tipos de máquinas de estado:
  • Reconocedoras: determinan si una secuencia es válida.
  • Traductoras: transforman una entrada en una salida.
  Estas se aplican, por ejemplo, en dispositivos automáticos, en sistemas de control y principalmente en la construcción de analizadores léxicos y sintácticos en compiladores.
• Autómatas finitos: Son el tipo más sencillo de máquina de estado. Se definen mediante un grafo dirigido:
  • Un único estado inicial.
  • Uno o más estados finales.
  • Transiciones etiquetadas por caracteres del alfabeto.
  Permiten recorrer cadenas para validar si pertenecen o no a un lenguaje definido.

Clase 5: Equivalencia y Minimización de Autómatas Finitos

• Estados accesibles: Se define un estado como accesible si hay alguna secuencia de transiciones que permite llegar a él desde el estado inicial. Los estados inaccesibles no afectan al comportamiento del autómata y pueden eliminarse sin alterar el lenguaje reconocido.
• Equivalencia entre autómatas: Dos autómatas finitos son equivalentes si aceptan exactamente las mismas palabras, es decir, si reconocen el mismo lenguaje. Esta comparación se puede realizar entre:
  • Dos AFD
  • Dos AFN
  • Un AFN y un AFD
• Estados compatibles: Dos estados se consideran compatibles si ambos son finales o ambos no lo son. Esta compatibilidad es clave para poder comparar dos autómatas en busca de equivalencia.
• Teorema de Moore: Proporciona un algoritmo de comparación entre autómatas:
  1. Eliminar estados inaccesibles.
  2. Comenzar desde los estados iniciales de ambos autómatas.
  3. Construir un árbol de comparación con pares de estados.
  4. Verificar la compatibilidad de los estados a medida que se avanza.
  5. Si aparece un par de estados incompatibles, se concluye que los autómatas no son equivalentes.
  6. Si no hay incompatibilidades, los autómatas sí son equivalentes.
• Minimización de un AFD: El proceso de minimización de un autómata busca obtener una versión más simple (con menos estados), sin modificar el lenguaje que reconoce. Se basa en:
  1. Eliminar estados inaccesibles.
  2. Identificar y eliminar estados redundantes o indistinguibles.
  3. Fusionar estos estados en uno solo.
• Estados distinguibles: Dos estados son distinguibles si, a partir de ellos, existen caminos que conducen a diferentes resultados (uno lleva a aceptar una palabra y el otro no). Son clave para saber si se pueden fusionar o no durante la minimización.
• Tabla de minimización: Se utiliza una tabla para identificar todos los pares de estados y marcar cuáles son distinguibles.

El proceso es sistemático y garantiza que el autómata resultante es mínimo, es decir, no se puede reducir más sin cambiar su lenguaje.

Clase 6: Conversión de AFN a AFD

• Autómatas Finitos No Deterministas (AFN): Son una generalización de los AFD. Permiten:
  • Múltiples transiciones con la misma etiqueta desde un mismo estado.
  • Transiciones sin consumir caracteres (ε-transiciones).
  • Ausencia de transiciones para ciertas entradas.
  • Etiquetas que son palabras completas, no solo símbolos individuales.
  En un AFN, puede haber más de un camino para una palabra dada o incluso ninguno. Debido a esa ambigüedad, una palabra se considera aceptada si existe al menos una trayectoria que la conduzca a un estado final.
• Ventajas y desventajas del AFN:
  • Ventaja: mayor flexibilidad para diseñar autómatas, lo que facilita la creación de modelos para lenguajes complejos.
  • Desventaja: la verificación de si una palabra pertenece al lenguaje requiere explorar todas las trayectorias posibles, lo cual puede ser costoso computacionalmente.
• Necesidad de convertir un AFN a AFD: Los AFD son más eficientes, más simples de ejecutar y aptos para implementarse en compiladores. Todo lenguaje reconocido por un AFN también puede ser reconocido por algún AFD equivalente. El objetivo es entonces derivar un AFD que reconozca el mismo lenguaje que un AFN dado.
• Método de conversión por conjuntos de estados: Es un procedimiento mecánico que construye un AFD a partir de un AFN:
  1. Se comienza con el conjunto que contiene el estado inicial del AFN.
  2. Para cada símbolo del alfabeto, se determina a qué conjunto de estados se puede llegar desde cada conjunto actual.
  3. Cada nuevo conjunto se trata como un nuevo “estado” del AFD.
  4. Se repiten los pasos hasta que no aparezcan conjuntos nuevos.
  Este método también es conocido como «construcción del subconjunto».
• Importancia del procedimiento:
  • Permite transformar un modelo flexible pero poco eficiente (AFN) en uno robusto y práctico (AFD).
  • Asegura la equivalencia de lenguajes: el AFD reconoce exactamente las mismas palabras que el AFN original.

Clase 7: Gramáticas Regulares

• Lenguaje de programación (LP): Un LP es una notación formal que permite describir algoritmos que una computadora puede ejecutar. Todo lenguaje tiene dos componentes principales:
  • Sintaxis: conjunto de reglas que determinan la forma válida de escribir sentencias.
  • Semántica: establece el significado de las sentencias válidas.
• Cómo describir la sintaxis: La sintaxis de un lenguaje se define mediante dos niveles:
  1. Reglas léxicas: establecen el conjunto de caracteres permitidos (alfabeto) y agrupan símbolos en categorías léxicas (como identificadores, números, palabras reservadas).
  2. Reglas sintácticas: definen cómo se combinan los lexemas para formar estructuras válidas (sentencias).
• Notación BNF (Backus-Naur Form): Es una notación formal y universal para describir la sintaxis de un lenguaje. Utiliza símbolos terminales (elementos concretos del lenguaje) y no terminales (categorías que deben definirse). Las reglas de producción se escriben como: A ::= B (A se reemplaza por B).
• Gramática formal: Es un conjunto de reglas que permite generar y/o reconocer las sentencias válidas de un lenguaje. Formalmente se define como una cuádrupla:

  G = {RP, T, NT, S}

  Donde:
  • RP: Reglas de producción.
  • T: Símbolos terminales.
  • NT: Símbolos no terminales.
  • S: Símbolo inicial.
• Clasificación de gramáticas (Jerarquía de Chomsky):
  • Tipo 3: Gramáticas Regulares → generan lenguajes regulares.
  • Tipo 2: Gramáticas Libres de Contexto → generan lenguajes de programación.
  • Tipo 1 y 0: se mencionan pero no se profundiza.
• Gramáticas regulares: Son las más simples y restrictivas. Aptas para describir patrones muy estructurados y repetitivos. Se usan para modelar lenguajes regulares, como los utilizados en analizadores léxicos. Toda gramática regular tiene un autómata finito equivalente y viceversa.

Clase 8: Gramáticas Libres de Contexto (GLC)

Contenidos principales: Esta clase se enfoca en las Gramáticas Libres de Contexto (GLC), fundamentales para modelar la estructura sintáctica de los lenguajes de programación. A diferencia de las gramáticas regulares, las GLC permiten representar estructuras más complejas como expresiones anidadas y bloques de código.

• Definición de Gramática Libre de Contexto (GLC): Una GLC se caracteriza por tener reglas de producción donde el lado izquierdo contiene un único símbolo no terminal, y el lado derecho puede tener una combinación de símbolos terminales y no terminales. Se expresan también con notación BNF, y permiten aplicar derivaciones sin importar el contexto donde aparece el símbolo a reemplazar.
• Uso práctico: Son adecuadas para representar sentencias de lenguajes de programación, como declaraciones, estructuras condicionales, expresiones aritméticas, etc. También se usan en la definición de otros lenguajes estructurados como HTML o XML.
• Símbolos y notación:
  • < > indica símbolo no terminal.
  • ::= se lee “se define como”.
  • | representa alternativas posibles.
  Estas gramáticas permiten definir estructuras recursivas, lo que las hace ideales para modelar repeticiones y anidamientos.
• Derivaciones: Existen dos formas principales de aplicar derivaciones:
  • Izquierda (leftmost): se reemplaza siempre el primer no terminal encontrado.
  • Derecha (rightmost): se reemplaza el último no terminal.
  Ambas formas deben conducir a la misma palabra final si la gramática está correctamente diseñada.
• Árbol de derivación: Es una herramienta visual que muestra el proceso de derivación de una palabra desde el símbolo inicial, ramificando cada regla aplicada. Muestra la estructura jerárquica de una sentencia. Es clave para la verificación sintáctica de un lenguaje.
• Importancia en compiladores: Las GLC son la base de los analizadores sintácticos en compiladores. Permiten validar si una secuencia de tokens generada por el análisis léxico corresponde a una sentencia válida en el lenguaje.

Clase 9: Autómata Finito de Pila (AFP) y Máquina de Turing

Contenidos principales: En esta clase se presentan dos modelos computacionales más potentes que los autómatas finitos: El Autómata Finito de Pila (AFP), que reconoce lenguajes libres de contexto. La Máquina de Turing (MT), que es capaz de reconocer cualquier lenguaje computable.

• Límites de los autómatas finitos: Los AFD y AFN no son suficientes para reconocer estructuras complejas como:
  • Palabras palíndromas.
  • Secuencias con igual cantidad de símbolos balanceados (por ejemplo, paréntesis).
  Para estos casos se necesita memoria adicional, como una pila.
• Autómata Finito de Pila (AFP): Es un autómata finito al que se le agrega una pila como estructura de memoria auxiliar. Esta pila permite recordar símbolos de manera ilimitada, lo cual lo hace apto para lenguajes con dependencias estructurales.
• Funcionamiento del AFP: La pila comienza vacía, o con un símbolo inicial que marca su fondo. En cada transición, el AFP:
  • Lee un símbolo de entrada.
  • Puede consultar (y quitar) el símbolo en el tope de la pila.
  • Puede agregar (apilar) uno o más símbolos.
  Las transiciones se anotan como: entrada / tope de pila / lo que se apila
• Condiciones de aceptación: Para que una palabra sea aceptada:
  1. Se debe haber leído completa.
  2. El autómata debe terminar en un estado final.
  3. La pila debe quedar vacía (solo con el símbolo inicial, que se retira al final).
• Aplicaciones del AFP:
  • Reconocimiento de lenguajes balanceados (paréntesis, estructuras anidadas).
  • Validación de palabras palíndromas.
  • Base para analizadores sintácticos que utilizan gramáticas libres de contexto.
• Formalización del AFP: Se representa como un séxtuplo:

  (K, Σ, Γ, Δ, s, F)

  Donde:
  • K: conjunto de estados.
  • Σ: alfabeto de entrada.
  • Γ: alfabeto de la pila.
  • Δ: relación de transición.
  • s: estado inicial.
  • F: conjunto de estados finales.
• Máquina de Turing (MT): Aunque no se desarrolla en profundidad, se menciona como el modelo más completo:
  • Posee una cinta infinita (memoria total).
  • Puede modificar tanto su estado como el contenido de la cinta.
  • Reconoce todos los lenguajes recursivamente enumerables.
  Es el modelo teórico de lo que una computadora puede hacer.

Clase 10: Semántica de Lenguajes de Programación y Fases de Compilación

Resumen detallado:

• Semántica de un lenguaje: Describe el efecto de ejecutar una instrucción válida. Responde preguntas como: ¿Qué hace esta sentencia cuando se ejecuta? ¿Cómo se modifica la memoria? ¿Qué cambios se producen en el sistema operativo?
• Procesamiento de lenguajes: Existen dos formas principales de procesar un programa escrito en un lenguaje de alto nivel:
  1. Compilación (traducción completa): Traduce el programa entero a código de máquina antes de ejecutarlo. El resultado es un programa objeto que puede ejecutarse repetidamente sin recompilación.

     Fases:

     • Análisis léxico
     • Análisis sintáctico
     • Análisis semántico
     • Síntesis (genera el código de máquina)
  2. Interpretación (traducción línea a línea): Traduce y ejecuta una línea a la vez. No se genera un archivo ejecutable. Requiere traducir nuevamente si se desea volver a ejecutar el programa.
• Análisis léxico: Identifica los componentes léxicos del programa (tokens). Agrupa caracteres en palabras clave, variables, operadores, etc. Se usa una tabla de símbolos para registrar los elementos del programa. Utiliza autómatas finitos para verificar la estructura de los tokens.
• Análisis sintáctico: Verifica que las secuencias de tokens cumplan la gramática del lenguaje. Usa gramáticas para construir árboles de derivación. Detecta errores de sintaxis como estructuras mal formadas.
• Análisis semántico: Verifica coherencia interna del programa. Revisa:
  • Tipos de datos compatibles.
  • Flujos de control válidos.
  • Nombres únicos y consistentes.
  • Argumentos de funciones bien definidos.
  • Errores potenciales en tiempo de ejecución (división por cero, variables no inicializadas, etc.)
  Se puede implementar mediante gramáticas con atributos.
• Síntesis: Toma la representación interna del programa (árboles o estructuras intermedias) y genera:
  • Código intermedio (como assembler).
  • Código de máquina ejecutable.
  Esta es la fase final del compilador.

Preguntas Frecuentes sobre Autómatas y Lenguajes

¿Es determinístico o no determinístico? Justificar.

Un autómata es determinístico si, para cada combinación de estado y símbolo del alfabeto, existe una única transición posible. Es no determinístico si hay más de una transición para el mismo símbolo desde un mismo estado, si existen transiciones vacías (ε), o si hay ambigüedad en las trayectorias.

¿Admite las palabras que empiezan con “a”?

Para que un autómata admita palabras que comienzan con “a”, debe existir al menos una transición con símbolo “a” desde el estado inicial. Si no hay ninguna transición con “a” desde el estado inicial, entonces no admite palabras que empiecen con ese símbolo.

¿Por qué es AFN o AFD?

Es un AFD si tiene una única transición definida para cada combinación de estado y símbolo del alfabeto. Es un AFN si hay más de una transición posible con el mismo símbolo desde un estado, si existen transiciones vacías (ε), o si alguna transición no está definida de forma única.

¿Es mínimo?

Un autómata es mínimo si no tiene estados inaccesibles (es decir, todos los estados pueden alcanzarse desde el estado inicial) y no tiene estados equivalentes que se puedan fusionar. Si existe algún estado inútil o duplicado en comportamiento, no es mínimo.

¿Cuándo una palabra es aceptada?

Una palabra es aceptada si, al comenzar desde el estado inicial y consumir todos los símbolos uno por uno, el autómata finaliza en un estado final. Si termina en un estado que no es final, la palabra no es aceptada.

¿Cuándo una palabra es procesada y lleva al estado de halt?

Una palabra lleva al estado de halt cuando se consume completamente y ya no hay más transiciones posibles. Solo se considera aceptada si ese estado de halt es un estado final. Si no es un estado final, entonces la palabra fue procesada pero no aceptada.

¿Cómo se escribe una gramática regular?

Una gramática regular se define como G = (T, NT, S, RP), donde T son los terminales, NT los no terminales, S el símbolo inicial, y RP el conjunto de reglas de producción. Las reglas deben tener la forma A → aB, A → a, o A → ε, donde A y B son no terminales y a es un símbolo terminal.