Gramatica Libre de Contexto y Autómata PushDown

ApuntesDeLaura

 

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

Captura de pantalla 2017-04-20 a las 2.26.37 p.m.

Diagrama de como Verlos

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:

Captura de pantalla 2017-04-20 a las 3.04.39 p.m.

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.

Captura de pantalla 2017-04-20 a las 2.46.04 p.m.

Ejemplo

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
Captura de pantalla 2017-04-17 a las 8.52.53 p.m.

Un Dibujito nunca esta de más

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:

Captura de pantalla 2017-04-17 a las 8.50.07 p.m.

Definición Formal

¿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

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s