Lenguajes y Lenguajes Formales

• Date:: 2023-03-23
• Course:: Informática Teórica
• Source:: Alfabeto y Cadenas de Caracteres

main_page #infoteo/lenguajes

Definición de Lenguaje (L)

?

• Es un conjunto de palabras válidas
• Definido a partir de las palabras válidas (validado por la gramática)
• Conjunto de cadena de caracteres pertenecientes de un alfabeto, junto con reglas establecidas en la gramática.
• En todos los casos, un lenguaje $L\subset {\Sigma }^{\ast }$

Tipos de lenguajes

?

• Nivel 1. Lenguaje de tipo 0. No posee restricción alguna (naturales)
• Nivel 2. Lenguaje de tipo 1. Sensibles al contexto
  • Las palabras dependen de la posición en la que aparezca
• Nivel 3. Lenguaje de tipo 2. Independientes del contexto.
• Nivel 4. Lenguaje de tipo 3. Lenguajes regulares
  • Los más simples (eg binario) La gramática determina las reglas con las que voy a poder formar las palabras

Jerarquías lenguajes vs máquinas abstractas

Definición de lenguajes formales

?

• Es una notación formal para expresar un algoritmo en términos de una computadora
• Sus dos componentes fundamentales son:
  • Sintáxis: determina las reglas de escritura para formular sentencias o palabras válidas del lenguaje.
  • Semántica: determnia el significado de cada sentencia válida.
• Todo lenguaje está definido sobre un alfabeto.