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

AFD Y AFND

EXPOSICIÓN DE AUTÓMATAS
by

Jacinto Céspedes

on 26 March 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of AFD Y AFND

DEMOSTRACIÓN PRÁCTICA 0 + - = 9 8 7 1 2 3 4 5 6 c •Ciencias de la Computación I, (Agosto 2007),Autómatas Finitos No Determinísticos Minimización de Autómatas Finitos Determinísticos, [diapositivas de PowerPoint]. Recuperado de: http://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r38051.PPT

•Equivalencia entre AFD y AFND,(s.f), Equivalencia entre AFD y AFND, [documento de Word]. Recuperado de: http://www.geocities.ws/okchicoz/metodosdeconversion.doc OBJETIVOS Objetivo General

Comprobar la equivalencia entre Autómatas Finitos Deterministas y No Deterministas y viceversa a través de ejercicios.

Objetivos Específicos:

•Aprender el algoritmo de conversión de un AFD y AFND y viceversa.
•Realizar la demostración práctica a través de varios ejemplos.
•Determinar las ventajas que se obtienen al realizar los diferentes algoritmos. Equivalencia de AFD y AFND Como parte inicial estableceremos las condiciones que se deben cumplir para realizar este algoritmo la misma que nos menciona que si el lenguaje de un autómata M es igual al de un autómata M’ existirá equivalencia ente el AFD y el AFND. Por lo tanto se establece que siempre se podrá obtener al menos un AFND a partir de un AFD. EQUIVALENCIA DE AFND Y AFD Para tener en cuenta la definición a través del siguiente teorema:
Teorema:

Sea L un lenguaje aceptado por un AFND. Entonces existe un AFD que acepta el mismo lenguaje L. Es decir, L(AFND) = L(AFD) EJEMPLOS AFND GRACIAS POR SU ATENCIÓN CONVERSIÓN DE AFND A AFD CONCLUSIONES Las transiciones que existan de un AFD de un estado a otro puede no depender de ninguna entrada, a estas transiciones se les denomina transiciones vacías, por lo que se puede optimizar el autómata en al momento de convertirlo en AFND. Los diferentes procesos o transiciones que un AFD realice serán cambiados por el AFND, siendo así que cada proceso realice la misma función pero de manera diferente e incluso más sencilla.
Por las diferentes circunstancias se llega a la conclusión que siempre será mejor hacer un AFND pues minimizará las transiciones y abarcará un lenguaje expuesto dependiendo el problema. Como conclusión se dice que un AFND es equivalente a un AFD ya que la única diferencia con los anteriores está en que en la transición en un estado determinado puede haber, para un mismo símbolo, más de un arco o no haber ninguno.
El presente trabajo nos ha permitido comprender acerca de las facilidades que nos ofrece un AFND ya que con él se puede obtener fácilmente un AFD.
Este tema es fundamental y de gran importancia para el desarrollo correcto de autómatas finitos. AFD Bibliografía
Full transcript