Autor Tema: Diseñar AFND-Epsilon

0 Usuarios y 1 Visitante están viendo este tema.

27 Febrero, 2018, 03:40 am
Leído 6554 veces

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Hola, si quisiera formar un AFND-Epsilon que acepte el lenguaje: \( \{hola, crayola\}* \)
Tendría que tener una transición vacía?, debería leer la palabra "hola" y al mismo tiempo "crayola"?
Cómo podría formarlo?

Gracias, saludos.


27 Febrero, 2018, 04:44 am
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Imagino que el alfabeto \( \Sigma \) es el abecedario (o al menos el subconjunto de las letras que aparecen en esas dos palabras).

Supón que tienes ya dibujado a \( M_1 \) (AFD que reconoce "hola)" y a \( M_2 \) (AFD que reconoce "crayola"). Para construir un AFND-épsilon con las características deseadas basta:

-considerar un estado inicial \( q_0 \) (que además sea también el único estado final)
-agregar una transición épsilon de \( q_0 \) al estado inicial de \( M_1 \)
-agregar una transición épsilon de \( q_0 \) al estado inicial de \( M_2 \)
-agregar una transición épsilon del estado final de \( M_1 \) a \( q_0 \)
-agregar una transición épsilon del estado final de \( M_2 \) a \( q_0 \)

Modificación posterior en rojo
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

27 Febrero, 2018, 06:30 am
Respuesta #2

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Imagino que el alfabeto \( \Sigma \) es el abecedario (o al menos el subconjunto de las letras que aparecen en esas dos palabras).

Supón que tienes ya dibujado a \( M_1 \) (AFD que reconoce "hola)" y a \( M_2 \) (AFD que reconoce "crayola"). Para construir un AFND-épsilon con las características deseadas basta:

-considerar un estado inicial \( q_0 \) (que además sea también el único estado final)
-agregar una transición épsilon de \( q_0 \) al estado inicial de \( M_1 \)
-agregar una transición épsilon de \( q_0 \) al estado inicial de \( M_2 \)
-agregar una transición épsilon del estado final de \( M_1 \) a \( q_0 \)
-agregar una transición épsilon del estado final de \( M_2 \) a \( q_0 \)

Modificación posterior en rojo

Hola, gracias por responder.

Sería entonces primero diseñar los AFD:

(Creo que así están correctos)

Y después unirlos?, aquí sí me perdí...



Saludos.

27 Febrero, 2018, 09:10 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Tienes mal a los autómatas \( M_1 \) y \( M_2 \). \( M_1 \) tiene que reconocer a una única cadena: "hola". No puede reconocer nada más. Lo mismo \( M_2 \), pero con "crayola". Una vez (bien) hechos estos autómatas, los unes con las directivas de mi mensaje anterior (por supuesto, pueden ahorrarse estados y usarse los mismos para "ola" de "hola" que para "ola" de "crayola", pero me parece más claro si \( M_1 \) y \( M_2 \) son independientes; en todo caso en una segunda versión haces ese tipo de optimizaciones).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

27 Febrero, 2018, 02:49 pm
Respuesta #4

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Mmm cuáles lazos son los que están mal en los autómatas que puse ?

27 Febrero, 2018, 07:20 pm
Respuesta #5

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Mmm cuáles lazos son los que están mal en los autómatas que puse ?

¿Tu autómata acepta solamente la cadena "hola"?
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print