Autor Tema: Problema al diseñar un autómata finito no determinista

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

14 Marzo, 2017, 02:06 am
Leído 2460 veces

Antoniio

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 258
  • Karma: +0/-0
  • Sexo: Masculino
Hola, buenas. Me dejaron que diseñara un autómata con ciertas características pero me ha salido mal, el problema es el siguiente:

"Diseñe un autómata finito no determinista que acepte el lenguaje dado por \( L = \left\{{w \in{\left\{{a,b}\right\}}*}\right\}  \) l \( w \) tiene un número par de \( a's \) y \( w \) tiene una o dos \(  b's \).

Yo intenté haciéndolo de esta manera:


Pero pues, al parecer \( b\in{L} \) y no la acepta, qué puedo modificar para que me salga correctamente??

Gracias de antemano !, saludos!

14 Marzo, 2017, 02:30 am
Respuesta #1

luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
Al ver tu dibujo se me ocurre que no te has detenido a pensar qué
propiedades cumplen los nodos que has dibujado. Además de que b está en el
lenguaje, tu propuesta acepta palabras que no están en el
lenguaje (por ejemplo, abb).
                               

Se me ocurre pensar en un NFA con ocho (o siete) estados, clasificados según:

* la cantidad de aes leídas es par o impar; y
* la cantidad de bes leídas es cero, una, dos, o más.

Una vez dibujados esos ocho estados, los uniría con los arcos adecuados.

Esta propuesta también me genera rápidamente un DFA.

saludos

luis

14 Marzo, 2017, 06:11 am
Respuesta #2

Antoniio

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 258
  • Karma: +0/-0
  • Sexo: Masculino
Mmmm y si mejor sigo los siguientes pasos que había pensado:
1) empezar en \( q0 \)
2) con\(  b \) ir a un estado final \( q1 \)
3) con \( a \) ir a un estado \( q2 \)
4) con otra \( a \) ir a un estado final \( q3 \)
5) si en \( q3 \) leo una \( b \) me voy al estado final \( q1 \)
6) si leo una\(  a \) ir al estado \( q2 \)
7) en \( q1 \) poner algo para las \( a's \) para asegurarme que sean pares.

Creo que así quedaría verdad?

14 Marzo, 2017, 12:40 pm
Respuesta #3

luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino

Creo que no es buena idea pensarlo paso a paso; me parece que sirve solamente para casos muy sencillos. De hecho, en este caso, al llegar a 7, te mareaste; qué significa "poner algo"? Además, parece que tu propuesta olvida que puede no aparecer ninguna b, o pueden aparecer dos.

Lo que yo te proponía era pensar en que cada nodo cumple con una propiedad distinguida, y luego puedo construír la navegación entre ellos. Ir paso a paso como propones me parece muy complicado.

saludos

luis


14 Marzo, 2017, 02:28 pm
Respuesta #4

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Esto lo tengo bastante olvidado, pero siguiendo la idea de luis, sería:

\( \begin{array}{}{}&{a}&{b}\\
{a^+b^0:q_0}&{q_1}&{q_2}\\
{a^-b^0:q_1}&{q_0}&{q_3}\\
{a^+b^1:q_2}&{q_3}&{q_5}\\
{a^-b^1:q_3}&{q_2}&{q_5}\\
{a^+b^2:q_4}&{q_5}&{q_6}\\
{a^-b^2:q_5}&{q_4}&{q_6}\\
{a^*b^3:q_6}&{-}&{-}\\
\end{array} \)

Los estados finales de aceptación serían \( q_2\textrm{ y }q_4; q_6 \) de rechazo. Donde \( a^+, a^-\textrm{ y }a^* \) significa un numéro par, impar o cualquiera de \( a,\textrm{ y }b^n \) significa un número \( n\textrm{ de }b \).

Debo hacer constar que estas cosas las vi por última vez hace más de veinte años, es decir, que la fiabilidad es relativa ...

Saludos,
Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)