Gramatica Libre de Contexto

Dejemos de prestar atención a los lenguajes regulares para una clase mayor de lenguajes, los llamados «lenguajes libre de contexto». Estos lenguajes tienen una notición de manera natural, una notación recursiva.

Se puede decir que es una notación para describir lenguajes.

Es mas poderosa que cualquier autómata finito, pero aun así no puede describir todos los lenguajes.

---

Partes de un Lenguaje Libre de Contexto

Una Explicación mas Detallada

• T: Terminales / Alfabeto de Símbolos de Entrada, podemos también llamarlo las terminales, o símbolos terminales.

• V: Conjunto de Variables, también los llaman no terminales o categorías sintácticas. Cada variable representa con conjunto de strings, digamos un sub lenguaje.

• S: Conjunto de variables «Especiales», representa un lenguaje bien definido, lo llaman también el símbolo inicial, también puede ser que haya otras variables que sean auxiliares.

• P: Una Función de Producción / Derivación, son un conjunto finito de reglas que muestran de manera recursiva una definición del lenguaje.

  Es más esto vale la pena verlo, veamos como:

Cada Producción Consta de:

Una variable que esta siendo (parcialmente) definido por la producción, esta variable la llaman de forma común la cabeza de la producción.

Una cadena de cero o mas variables y quizá algunos terminales, el string lo suelen llamar el cuerpo de la producción, que representa una forma de generar los strings, donde simplemente basta con sustituir las variables que estén dentro del cuerpo.

Ideas Generales

• Usar las variable para formar conjuntos de strings, osea lenguajes.

• Estas variables están definidas de manera recursiva, en términos de otras.

• Las reglas recursivas solo tienen que ser concatenaciones.

• Puedes genera una unión de lenguajes con dos reglas alternativas.

 

Derivación

1. Para crear una palabra del Lenguaje, lo que tendremos que hacer será:
2. Iniciar con nuestra variable de cadena o string
3. Sustituir esa expresión en alguna regla de Producción.
4. Repetir el Paso 3 hasta que no queden mas que terminales.

 

---

Ejemplo:

Veamos un ejemplo de estos lenguajes de esta manera:

Crear Strings Binarios de la Forma  0^n 1^n

• Terminales : { 0, 1 }
• Variables : { S }
• Simbolo de Inicio : { S }
• Producto :
  • S -> 01
  • S -> 0S1

 

 

 

---

Notación BNF:

Hay varias formas estándar de trabajar estos lenguajes, esta notación es muy muy común en programación, es conocida como Backus-Naur Form así que veámosla:

• (V) Variables – Se ponen así: <Variable>
• (T) Terminales – Se ponen así: TerminalUno / TerminalDos
• (->) Producción – Se ponen así: ::=
• (S -> a | b) Simplificación para dos reglas usando la misma regla: S -> a y S -> b

Ejemplos:

Usando esta notación nos permite hacer cosas como esta, Naturales:

• Terminales : { 0, 1, 2, 3, 4, 5, 6,7 8, 9 }
• Variables : { U, D }
• Simbolo de Inicio : { U }
• Producto :
  • U  ::=  UD | D
  • U  ::=  0|1|2|3|4|5|6|7|8|9

 

 

 

 

 

---

Automatas de Pila

Podemos pensar en los Autómatas PushDown de la siguiente manera:

• Un Automata ε-NFA
• Un Pila bastante especial

Así con cada simbolo que va leyendo el autómata puede hacer 2 acciones:

• Moverse a otro estado
• También si lo necesita afecta (push, pull) la pila

De manera totalmente formal podemos definir cualquiera de los PDA como:

¿Parece bastante sencillo verdad?

Pues la verdad es que no es tan complejo como tu te podrías imaginar.

Estado Inmediato

Podemos describir el «estado» en cada momento con toda la información del autómata con 3 cosas:

• El estado actual del autómata
• El símbolo que estamos leyendo
• El simbolo en el tope de la pila