Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Untitled Prezi

No description
by

dayan lopez

on 20 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

Dayan Lizeth Lopez
Diana Cuaichar
Luis Alberto Madera
Oliverio Castañeda
Ivan David Aguirre Gramaticas Bien Formadas Definición Diagrama de gramatica Bien Formada Una gramática bien formada es aquella que no posee reglas innecesarias, reglas no generativas, símbolos no accesibles, reglas de redenominación ni reglas reductoras. Si, además, posee la regla S ::= tampoco se permite la existencia del axioma inducido. Una regla es de redenominación o UNITARIA cuando: Reglas Unitarias Son aquellos símbolos no terminales, que nunca podrán ser alcanzados desde el axioma inicial de la gramática. Símbolos Innacesibles Axioma Inducido Una gramática es considerada limpia, si no posee reglas innecesarias, símbolos inaccesibles, ni símbolos superfluos (ya sean terminales o no terminales) Gramática Limpia Reglas Reductoras Las reglas reductoras son del tipo Sea la gramática
Esta gramática genera el lenguaje
Posee una regla reductora
Esta regla se elimina y se añaden producciones resultantes de eliminar A en la parte derecha de la producción S ::= aAb. Es decir, se añade la producción S ::= ab. La gramática resultante es equivalente a la gramática G pero todavía no está depurada Ejemplo Reglas Reductoras Sea la gramática
Esta gramática posee una regla de redenominación S ::= A. Se elimina y se añade la producción S ::= ab. La gramática resultante es
Esta gramática todavía no está depurada ya que posee un símbolo A inaccesible desde el axioma. Sin embargo, es fácil observar que es equivalente a la gramática de partida
ya que: Ejemplo de Reglas de Redenominacion En las gramáticas bien formadas no se permite que el axioma esté inducido (aparezca en la parte derecha de alguna producción) si la regla Para eliminar el axioma inducido en estos casos, simplemente se añade un nuevo símbolo no terminal S’ que pasa a ser el nuevo axioma y se añade la producción S’ ::= S. Por tanto, la nueva gramática será:
Fijarse que se consigue eliminar el axioma inducido pero a expensas de introducir una regla de redenominación que habrá que eliminar posteriormente para depurar la gramática. Reglas no Generativas Son reglas que no se emplean nunca en la generación de palabras del lenguaje. Por tanto, su eliminación no modifica el lenguaje generado por la gramática de partida. Reglas Innecesarias Son las que tienen la forma: Este tipo de reglas de producción, ya que no producen derivaciones útiles en la gramática. Símbolos Superfluos Estos pueden ser de dos tipos, Terminales, y No Terminales Símbolo Terminal Superfluo: Es aquel símbolo Terminal, que nunca podrá ser alcanzado por una derivación partiendo desde el axioma inicial.O sea, no existe ninguna producción Reglas de Redenominacion Son las reglas de reescritura del tipo: Ejemplos Para cada una de las siguientes Gramáticas, generar la gramática bien formada correspondiente. es decir, eliminando reglas no Generativas y Reglas de Redominacion. Ejemplo 2 Para cada una de las siguientes Gramáticas, generar la gramática bien formada correspondiente.es decir, eliminando reglas no Generativas y Reglas de Redominacion.
Full transcript