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

Conversión de una Expresión Regular a un AFD óptimo

No description
by

Daniel Castro

on 11 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Conversión de una Expresión Regular a un AFD óptimo

Conversión de una Expresión Regular a un AFD óptimo
(Estados Significativos)

Los estados Significativos son todos los estados del AFN que tienen transiciones de salidas diferentes de λ.
Los estados significativos son q2 y q4. Como el estado de aceptación no es significativo se le concatena un símbolo adicional (#) para que este estado sea significativo.
Pasos para aplicar ES
1. Aumentar la expresión regular
2. Construcción del árbol de análisis sintáctico (árbol binario)
Hojas: Componentes Léxicos
Raíz y Nodos Interiores: Operadores (·, *, |)
Tomando AFN Thompson
1. Aumentar la expresión regular (a|b)*#
Enumeramos las hojas de izquierda a derecha.
Aplicaremos cuatro Funciones
Anul: Anulable (booleana)
Ppos: Primera Posición
Upos: Última Posición
Spos: Siguiente Posición
Para obtener
Anul
,
Ppos
y
Upos
observamos la tabla
Tabla Anul, Ppos y Upos
Árbol de Análisis sintáctico de (a | b)*# con sus anulables (
Anul
)
Árbol de Análisis Sintáctico de (a|b)*# con sus Ppos
Árbol de Análisis Sintáctico de (a|b)*# con su Ppos y Upos
Siguiente Posición (Spos)
Reglas para obtener siguiente Posición
Para la concatenación
(.): Si i Є Upos (C1) ---> Spos (i) ← U (Ppos (C2)) Unión de todas las Ppos si hay más de una.

Para la cerradura de kleene
(*): Si i Є Upos (C1) ⇒ Spos (i) ←U (Ppos (C1).) Se procede a realizar el
Anulable(Anul)
a cada estado del autómata finito, dependiendo
de la tabla anterior
Construimos el Spos Resolviéndolo segun las reglas establecidas (a|b)*.
nota
: El nodo # no se hace en spos
Se realizan los Trans.

A = PposRaiz = {1, 2, 3}
Trans (A, a) = A
Trans (A, b) = A

Se construye la tabla de Transición
Finalmente el Autómata óptimo (a|b)*
Construcción del árbol sintáctico
(a| b)*#
Daniel ortiz Castro
Hozman Barrios
Felix Sanchez

INGENIERIA DE SISTEMA
Full transcript