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

Reducción de un Automata Finito Deterministico (AFD).

No description
by

benjamin rodrigo lopez godoy

on 21 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Reducción de un Automata Finito Deterministico (AFD).

Reducción de un Automata Finito
Deterministico (AFD).

Definición de un ADF.
Un autómata finito determinista
(abreviado AFD) es un autómata
finito que además es un sistema determinista; es decir, para cada
estado en que se encuentre el
autómata, y con cualquier símbolo
del alfabeto leído, existe siempre
a lo más una transición posible
desde ese estado y con ese símbolo.
Paso 1:
-Primero tenemos que buscar
estados
"inaccesibles"
. Que quiere
decir esto, son aquellos estados a
los cuales no podemos llegar de
ninguna manera. Por que hacer esto?
sencillamente los estados
inaccesibles solo estorban. No
afectan en nada a nuestro automata y
solo lo hacen mas grande. Así que
los eliminamos.

En este caso obsevamos que no hay
manera de llegar al estado
q3
, no lo tomaremos en cuenta
(lo eliminamos).
Agrupamos de nuevo para obtener nuevos grupos(subconjunto del subconjunto):
PASO 4
Antes de realizar el nuevo diagrama, como podemos observar en la imagen obtenemos una nueva tabla de transición. Donde los estados ya no son {q0,q1,q2,q4,q5,q6,q7}, ahora son {C111,C112,C12,C13,C2}. Donde el estado inicial es q0 ahora sera C111 y el estado de aceptación en este caso solo cambio de q2 - C2.
POR ÚLTIMO SOLO COMPARAMOS LOS DOS AUTOMATAS:
PASO 3
Ahora lo que realizaremos es utilizar el lenguaje que acepta el automata que en este caso son
"0 y 1"
y verificaremos a que estado nos lleva y en que
CONJUNTO
se encuentra el estado.
PASO 2
Una vez eliminados los estados inaccesibles
pasamos a realizar un par de agrupaciones
donde; agruparemos por estados de no aceptación y estados de aceptación (NO IMPORTA EL ORDEN).
Volvemos agrupar los estados que coinciden:
Se define como una 5-tupla (Q, E(sigma), q0, F, S) donde:
-Q: es un conjunto de estados;
-E (SIGMA): es un alfabeto;
-q0: estado inicial;
-F: son los estados de aceptación;
-S: producto ordenada de los estados (tabla de transición).
Ejemplo
Para reducir un automata hay que seguir estos pasos.
NOTA: C1 Y C2 QUE SON LOS NOMBRES DE LOS CONJUNTOS, PUEDEN SER CUALQUIER PALABRA QUE SE QUIERA USAR. SOLO HAY QUE TENER CUIDADO DE NO CONFUNDIRNOS DE LA REFERENCIA DE LaS PALABRAS QUE USAMOS.
NOTA: ES RECOMENDABLE TENER LA TABLA DE TRANSICIÓN DEL DIAGRAMA INICIAL
PARA IR VERIFICANDO A QUE ESTADO NOS DIRIGIMOS Y EN QUE CONJUNTO ESTA.
SOLO CAMBIAMOS LOS ESTADOS A EL CONJUNTO DONDE SE ENCUENTRA.
C2 no lo afectamos ya que solo hay un solo estado en
ese grupo. En caso de haber mas estados de aceptación se aplica los mismos pasos que estamos aplicando en los estados de no aceptación.
Por lo tanto decimos que C2 es un conjunto completo por que no hay otro estado con el cual se pueda agrupar.
Obteniendo nuevos grupos (subconjuntos de los conjuntos iniciales);
para no revolvernos podemos dejar el nombre del conjunto principal para indicar de donde salio y agregamos cualquier símbolo para así saber que es un subconjunto.
Volvemos aplicar el lenguaje a cada estado para verificar a donde nos lleva cada estado y en que conjunto se encuentra:
q5 esta solo como q2, por lo tanto ya no podemos
seguir agrupandolo de nuevo. Obteniendo otro conjunto terminado o completado.
-Q={q0,q1,q2,q3,q4,q5,q6,q7}
-E (SIGMA)={0,1}
-q0: q0
-F={q2}

-S=
Observamos que en C12 los estados coinciden entonces el conjunto esta termindo o completado y así queda. No se puede hacer mas.
A simple vista parece que ya terminamos ya que q6 quedara solo y q0-q4 coinciden. Pero es recomendable hacer una vez mas la iteración para asegurarnos de que realmente coinciden ya que existe la posibilidad que sea erróneo.
Por último obtenemos:
Cada conjunto esta terminado, ya no podemos dividirlos mas. Ahora pasamos al último paso
Con la nueva tabla que obtuvimos haces el diagrama quedando de esta manera:
-Q={q0,q1,q2,q3,q4,q5,q6,q7}
-E (SIGMA)={0,1}
-q0: q0
-F={q2}

-S=
-Q={C11,C112,C12,C13,C2}
-E (SIGMA)={0,1}
-q0: C11
-F={C2}

-S=
Full transcript