Los lenguajes independientes

INTRODUCCIÓN

Los lenguajes independientes del contexto que también se conocen con el nombre de gramáticas de contexto libre son un método recursivo sencillo de especificación de reglas gramaticales con las que se pueden generar cadenas de un lenguaje.

Es factible producir de esta manera todos los lenguajes regulares, además de que existen ejemplos sencillos de gramáticas de contexto libre que generan lenguajes no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales.

OBJETIVOS

OBJETIVO GENERAL:

• Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

OBJETIVOS ESPECÍFICOS:

• Generalizar los conceptos de autómatas finitos, y gramáticas regulares.

• Reconocer el potencial de procesamiento del lenguaje del autómata con los autómatas de pila.

1. Describa y explique cada uno de los elementos que permiten definir formalmente un Autómata a Pila (AFPD) como una 7-upla.

Δ: Q × (Σ U {ε}) × Г → (Q × Г *)

Definición

Un autómata de pila determinista (AFPD) es una 7-upla, P = (Q, Σ, Г, Δ, q0, T, Z) donde:

• Q es un conjunto finito de estados.

• Σ es el alfabeto de entrada.

• Г es el alfabeto de la pila.

• q0  Q es el estado inicial.

• Z  Г símbolo inicial de la pila.

• T  Q conjunto de estados finales.

• Δ es la función de transición tal que:

Δ: Q × (Σ  {ε}) × Г → (Q × Г*)

Observación

En un momento, la unidad de control del autómata escanea un símbolo a sobre la cinta de entrada y el símbolo s en el tope de la pila.

Este paso computacional representa: La unidad de control pasa a q’ y se mueve a la derecha en la cinta de entrada, borra el símbolo s del tope, escribe en la cadena  y pasa a escanear el nuevo tope.

2. Construya el Autómata a pila para el lenguaje

APV=({a,b},{S,A},{p,q},S,p,f,∅)

f(p,a,S)={(p,A)}

f(p,a,A)={(p,AA)}

f(p,b,A)={(q, λ)}

f(q,b,A)={(q, λ)}

APF=({a,b},{S,A},{p,q,r},S,p,f,{r})

f(p,a,S)={(p,AS)}

f(p,a,A)={(p,AA)}

f(p,b,A)={(q,λ)}

f(q,b,A)={(q,λ)}

f(q,λ,S)={(r,S)}

Movimientos para (p,aabb,S) (p,abb,S) (p,aab,S)

• Grafíquelo en JFLAP y realice el “Traceback” para las transiciones.

• Plasme las imágenes y capturas en el documento.

• Trabájelo en el simulador JFLAP

3. Diseñar un autómata de pila M tal que Trabájelo en el simulador JFLAP

Es el autómata pedido. Es no determinista, siempre se puede adaptar de forma que vacíe su pila antes de aceptar la cadena. De hecho, ya lo hace.

Si se pidiera un autómata determinista para podría tenerse este:

Su funcionamiento es el pedido.

Cuando m=0 y n=0, se acaba en el estado 1.

Cuando m=0 y n 0, se acaba en el estado 2.

Cuando m 0 y n=0, se acaba en el estado 1.

Cuando m 0 y n 0, se acaba en el estado 4.

Es determinista, pero si acaba en los estados 1 ó 2 no vacía su pila al aceptar la cadena. El teorema es aplicable, pues los deterministas están incluidos en los no deterministas. Pero el resultado es un autómata de pila no determinista.

Se trata de un autómata de pila determinista que no puede modificarse para que (sin alterar el lenguaje aceptado) vacíe su pila al aceptar la cadena.

Estos dos ejemplos muestran que el conjunto de lenguajes deterministas se subdividen en dos: los que deben vaciar su pila al terminar y los que pueden no vaciarla.

Por supuesto (debido a que un conjunto está incluido en el otro), puede haber algunos (pero sólo algunos) autómatas de pila deterministas que puedan modificarse para que vacíen su pila al aceptar la cadena. Si se pidiera un autómata determinista para

Su funcionamiento es el pedido. Como m ≠ 0 y n ≠ 0, sólo se acaba en el estado 4; y en este estado la pila está vacía.

4. ¿Cuál es el lenguaje aceptado por el siguiente autómata de pila?

• Trabájelo en el simulador JFLAP.

5. Construir un AFPD que reconozca:

Sea

...