2.2.9 AL/Lenguajes Formales y Autómatas

Temas:
Core

• Autómatas formales:
  1. Estado Finito
  2. Pila
  3. Linealmente Acotado
  4. Máquina de Turing
• Lenguajes formales, gramáticas y Jerarquía de Chomsky:
  1. Regulares (Tipo-3):
     1. Expresiones Regulares
  2. Libres de Contexto (Tipo-2)
  3. Sensibles al Contexto (Tipo-1)
  4. Recursivamente Enumerables (Tipo-0)
• Relaciones entre autómatas formales, lenguajes y gramáticas
• Autómatas deterministas y no deterministas
• Demostraciones del Lema de Bombeo:
  1. Demostración de la limitación de Estado Finito/Lenguaje Regular
  2. Limitación de Autómatas de Pila/Lenguaje Libre de Contexto
• Modelos equivalentes de computación algorítmica:
  1. Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)
  2. Cálculo Lambda
  3. Funciones Mu-Recursivas

Aprendizaje esperado (Learning Outcomes):
Core:

1. Para cada autómata formal en esta unidad:
   1. Explicar su definición comparando sus características con los otros autómatas de esta unidad
   2. Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
   3. Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.
   [Explicar]
2. Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]
3. Desarrollar una expresión regular para un lenguaje regular dado expresado en lenguaje natural [Crear]
4. Explicar la diferencia entre expresiones regulares (aceptadores Tipo-3) y las expresiones regulares (aceptadores Tipo-2) usadas en lenguajes de programación [Explicar]
5. Para cada modelo formal en esta unidad:
   1. Explicar su definición comparando sus características con las otras en esta unidad
   2. Explicar ejemplos de entradas que son y no pueden ser aceptadas por el lenguaje/gramática.
   [Explicar]
6. Para cada autómata formal en esta unidad explicar (comparar/contrastar) sus capacidades deterministas y no deterministas [Explicar]
7. Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]
8. Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]