Lenguajes formales

Son representaciones abstractas de procesos que sirven para analizar su comportamiento. Tienen reglas estrictas, lo que los distingue de los lenguajes naturales. Los lenguajes formales se clasifican según la

Jerarquía de Chomsky y Variantes

• Lenguajes regulares Autómatas finitos)
• Lenguajes libres de contexto (Autómatas de pila)
• Lenguajes sensibles al contexto (Máquina Linealmente Acotada)
• Lenguajes recursivamente enumerables (Máquinas de Turing)
• Variantes de Máquinas de Turing:
• Máquinas de Turing alternantes
• Máquinas de registro
• Sistemas de Post

Modelos de Reescritura y Transformación

• Gramáticas de grafos
• Cálculo lambda
• Sistemas de reescritura general

Modelos Estocásticos y Probabilísticos

• Procesos de Markov
• Máquinas probabilísticas de Turing
• Redes Bayesianas

Modelos Inspirados Biológicamente

• Computación ADN
• Computación membranal (P-systems)
• Computación evolutiva

Modelos Cuánticos

• Máquinas de Turing cuánticas
• Circuitos cuánticos

Modelos Lógicos y de Decisión

• Lógica:
  • Lógica proposicional
  • Lógica de predicados.
• Lógica temporal.
• Lógica modal
• Cuando estos modelos no pueden interpretar los lenguajes naturales humanos se recurre a Lógica informal.

Modelos Continuos

• Máquinas analógicas
• Autómatas continuos

Lenguajes de Programación y su Relación con Lenguajes Formales

Los Lenguajes de programación integran varios niveles de la teoría de lenguajes formales:

Análisis Léxico y Sintáctico

• La tokenización utiliza autómatas finitos (lenguajes regulares)
• El parsing usa gramáticas libres de contexto y autómatas de pila
• La sintaxis del lenguaje se define mediante gramáticas formales

Poder Computacional

• Los lenguajes de programación modernos son Turing completos
• Pueden resolver cualquier problema computable
• Equivalentes en poder a las Máquinas de Turing

Niveles de Abstracción

1. Nivel Léxico (Tokens)
2. Utiliza lenguajes regulares
3. Implementado con autómatas finitos

4. Reconoce identificadores, números, símbolos

5. Nivel Sintáctico (Estructura)

6. Utiliza lenguajes libres de contexto
7. Implementado con autómatas de pila

8. Define la estructura gramatical del código

9. Nivel Semántico (Significado)

10. Requiere lenguajes sensibles al contexto
11. Verifica tipos y reglas semánticas

12. Implementa el comportamiento del programa

13. Nivel de Ejecución

14. Turing completo
15. Puede computar cualquier función computable
16. Implementa la lógica completa del programa

Ver también

Matemáticas