Gramáticas y Lenguajes Formales e Introducción a los Autómatas Finitos.

Gramáticas y Lenguajes Formales e Introducción a los Autómatas Finitos.

1. Gramáticas

   • Gramáticas y Lenguajes Formales e Introducción a los Autómatas Finitos.
     • Tipo 3
       • Gramáticas regulares que generan lenguajes regulares
     • Tipo 1
       • Gramáticas contextuales que generan lenguajes contextuales
     • Tipo 0
       • Gramáticas libres que generan lenguajes sin ningún tipo de restricción
     • Tipo 2
       • Gramáticas incontextuales que generan lenguajes incontextuales
     • Características
       • Cuanto menor es el tipo, mayor es el poder expresivo del lenguaje generado y más complejidad tiene su tratamiento por parte de una máquina

2. Autómatas Finitos

   • Consiste en dos conjuntos finitos, uno de símbolos no terminales y otro de símbolos terminales, un subconjunto finito de producciones y de un símbolo inicial.
     • Tipo 1
       • Autómatas finitos deterministas (AFDs)
         t ∈ E × A → E (Con cada símbolo de entrada se pasa de un estado del autómata a otro)
     • Tipo 2
       • Autómatas finitos no deterministas (AFNDs)
         t ∈ E × (A ∪ {λ}) → ℘(E) (Con algún símbolo de entrada, o con la cadena vacía, se pasa de uno de los estados del autómata a otro conjunto no vacío de estados - ℘ significa partición -)
     • Características
       • Sirve para reconocer cadenas de símbolos de un lenguaje regular, para lo que: 1. Parte del estado inicial 2. Recibe uno a uno los símbolos de la cadena de entrada
         En un AFND este paso a veces se ignora, pudiendo ocurrir una transición espontánea (λ-transición) 3. Aplica la función de transición para cambiar su estado
         Un AFND puede estar en varios estados a la vez 4. Si quedan símbolos por procesar, vuelve al paso 2 5. Si no quedan símbolos por procesar…
         Si se ha alcanzado algún estado final la cadena es reconocida como perteneciente al lenguaje [Fin]
         Si no se ha alcanzado ningún estado final la cadena es rechazada por ser no perteneciente al lenguaje [Fin]

3. Lenguajes Formales

   • Es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.
     • Características
       • El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9
         • A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada (o palabra) del lenguaje
     • Gramática
       • Es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del alfabeto
     • Alfabético
       • Es un conjunto finito no vacío de símbolos