Segunda Serie de LFyA

Este es el link del documento, lo subi a un servidor, espero y funcione correctamente, por si el archivo adjunto no le llegaba de forma correcta.

link: http://www.gigasize.com/get.php/-1100069872/Serie2deautomatas1.doc

GRAMATICA LIBRE DE CONTEXTO

Obtenga la GLC para el lenguaje de los paréntesis balanceados


S->TT->TF
F->PT->P
P->()

BNF(Backus-Naur form)

El Backus-Naur form (BNF) (también conocido como Backus-Naur formalism, Backus normal form o Panini-Backus Form) es una metasintaxis usada para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales.
El BNF se utiliza extensamente como notación para las gramáticas de los lenguajes de programación de la computadora, de los sistemas de comando y de los protocolos de comunicación, así como una notación para representar partes de las gramáticas de la lengua natural (por ejemplo, el metro en la poesía de Venpa). La mayoría de los libros de textos para la teoría y/o la semántica del lenguaje de programación documentan el lenguaje de programación en BNF. Algunas variantes, tales como la augmented Backus-Naur form (ABNF), tienen su propia documentación.

Ejemplo

Esto se traduce a español como:

· Un dirección postal consiste de un nombre, seguido por una dirección, seguida por un código postal.

· Una parte "personal" consiste en un nombre o una inicial seguido(a) por un punto.

· Un nombre consiste de: una parte pesonal seguida por un apellido seguido opcionalmente por una jerarquía o el trato que se la da a la persona (Jr., Sr., o número dinástico) y un salto de línea (end-of-line), o bien una parte personal seguida por un nombre (esta regla ilustra el uso de la repetición en BNFs, cubriendo el caso de la gente que utiliza múltiples nombres y los nombres medios y/o las iniciales).

· Una dirección consiste de una especificación opcional del departamento, seguido de un número de casa, seguido por el nombre de la calle, seguido por un salto de línea (end-of-line).

· Un apartado posta consiste de una ciudad, seguida por una coma, seguida por un código del estado (recuerden que es un ejemplo que ocurre en EU), seguido por un código postal y este seguido por un salto de línea (end-of-line).

Observe que muchas cosas (tales como el formato de una parte personal, de una especificación del apartamento, o código postal) están dejadas sin especificar aquí. Si es necesario, pueden ser descritas usando reglas adicionales de BNF, o dejadas como

Para mayor informacion consulte los soguientes enlaces:
http://es.wikipedia.org/wiki/Backus-Naur_form
http://members.fortunecity.es/toto1/informeebnf.doc (documento en world)

DISEÑO DE UNA ER

Diseñe la ER que construye el lenguaje en {a,b,c} en el que las palabras deben empezar con “abc”,, contienen dos veces la subcadena “aca” y terminan en “cba”

EJEMPLO: abcacaacacba

abc*((ab+b+c)*(a+^))*aca*((ab+b+c)*(a+^))*aca*((a+b+ca)*(c+^))*c