Autor Tema: Diseñar AFD para \(L:=\{w\in\{a,b\}^*:\text{\(w\) no contenga \(aa,bb\)}\}\)

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

03 Enero, 2020, 03:45 am
Leído 493 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Construya AFDs que acepten el siguiente lenguaje. Escribalo formalmente y dibujelo.

\( L:=\{w\in \{a,b\}^*, w \text{ no tiene } aa \text{ ni } bb \text{ como subcadena}\}. \)

"Haz de las Matemáticas tu pasión".

03 Enero, 2020, 06:14 am
Respuesta #1

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Construya AFDs que acepten el siguiente lenguaje. Escríbalo formalmente y dibújelo.

\( L:=\{w\in \{a,b\}^*, w \text{ no tiene } aa \text{ ni } bb \text{ como subcadena}\}. \)

¿Qué intentaste?

Yo hice un AFD pero no sé si está bien. Dejo algunas pistas:

Toda palabra es o bien la palabra nula o comienza con \( a \) o \( b \). Ahí ya tenemos 3 estados (que son de aceptación). Elijamos el estado al que le llega una \( a \). Esa palabra debe obligatoriamente continuar con una \( b \), pero si lo unimos con el estado que nos enviaba una \( a \) tendremos la posibilidad de formar dos \( b \) contiguas, por tanto la nueva transición no debe volver al estado original sino debe ser enviada a otro; elijamos al que le llega una \( b \). Por otro lado tenemos que poder formar una cadena que empiece con \( b \) y siga obligatoriamente con \( a \); por tanto esa transición (como vimos antes) no debe regresar al estado inicial sino que va a parar a otro lado; elegimos el estado al que le llega una \( a \).

Preguntas:

- ¿Cuántos estados en total hay?
- ¿Cuántos son de aceptación?
- ¿Queda alguna palabra que haya que aceptar pero que no se forme con este AFD?

AFD propuesto
[cerrar]

Si alguno quiere revisar estaría agradecido.

Saludos y Feliz Año Nuevo

Mods
Título cambiado de "AFD 2" a "Diseñar AFD para \(L:=\{w\in\{a,b\}^*:\text{\(w\) no contenga \(aa,bb\)}\}\)".
[cerrar]

04 Enero, 2020, 02:35 am
Respuesta #2

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

Construya AFDs que acepten el siguiente lenguaje. Escríbalo formalmente y dibújelo.

\( L:=\{w\in \{a,b\}^*, w \text{ no tiene } aa \text{ ni } bb \text{ como subcadena}\}. \)

¿Qué intentaste?

Yo hice un AFD pero no sé si está bien. Dejo algunas pistas:

Toda palabra es o bien la palabra nula o comienza con \( a \) o \( b \). Ahí ya tenemos 3 estados (que son de aceptación). Elijamos el estado al que le llega una \( a \). Esa palabra debe obligatoriamente continuar con una \( b \), pero si lo unimos con el estado que nos enviaba una \( a \) tendremos la posibilidad de formar dos \( b \) contiguas, por tanto la nueva transición no debe volver al estado original sino debe ser enviada a otro; elijamos al que le llega una \( b \). Por otro lado tenemos que poder formar una cadena que empiece con \( b \) y siga obligatoriamente con \( a \); por tanto esa transición (como vimos antes) no debe regresar al estado inicial sino que va a parar a otro lado; elegimos el estado al que le llega una \( a \).

Preguntas:

- ¿Cuántos estados en total hay?
- ¿Cuántos son de aceptación?
- ¿Queda alguna palabra que haya que aceptar pero que no se forme con este AFD?

AFD propuesto
[cerrar]

Si alguno quiere revisar estaría agradecido.

Saludos y Feliz Año Nuevo

Mods
Título cambiado de "AFD 2" a "Diseñar AFD para \(L:=\{w\in\{a,b\}^*:\text{\(w\) no contenga \(aa,bb\)}\}\)".
[cerrar]

Muchas Gracias manooooh, me queda claro el diagrama
... Pero por ejemplo, como queda escrito formalmente?
"Haz de las Matemáticas tu pasión".

04 Enero, 2020, 02:40 am
Respuesta #3

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿ cómo queda escrito formalmente?

¿Cuál es la definición de AFD que manejás?

Saludos

04 Enero, 2020, 04:45 am
Respuesta #4

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

¿ cómo queda escrito formalmente?

¿Cuál es la definición de AFD que manejás?

Saludos

Muchas Gracias, es la siguiente:

Definicion: Un automata finito deterministico (AFD) es una tupla \( M=(K, \Sigma,\delta,s, F) \) tal que

- \( K \) es un conjunto finito de estados
- \( \Sigma \) es un alfabeto finito
- \( s\in K \) es el estado inicial
- \( F\subseteq K \) son los estados finales
- \( \delta: K\times \Sigma \to K \) es la funcion de transicion

¿Y ahora que hago?
"Haz de las Matemáticas tu pasión".

04 Enero, 2020, 05:36 am
Respuesta #5

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿Y ahora qué hago?

Mirar el diagrama del AFD e identificar sus partes.

¿Quiénes son los estados? ¿El alfabeto? ¿El estado inicial y los finales? ¿Y las transiciones?

En general para la parte de las transiciones no se suele dar con la notación de una función como \( \delta(1,a)=2 \) sino que se lo indica con una flecha así: \( 1\to a2 \).

Saludos

05 Enero, 2020, 05:14 am
Respuesta #6

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

¿Y ahora qué hago?

Mirar el diagrama del AFD e identificar sus partes.

¿Quiénes son los estados? ¿El alfabeto? ¿El estado inicial y los finales? ¿Y las transiciones?

En general para la parte de las transiciones no se suele dar con la notación de una función como \( \delta(1,a)=2 \) sino que se lo indica con una flecha así: \( 1\to a2 \).

Saludos

Muchas Gracias, entonces escrito formalmente el AFD es \( M=(K,\Sigma,\delta,s, F) \) en donde, \( K=\{1,2,3\} \), \( \Sigma=\{a,b\} \), \( s=1 \), \( F=\{2\} \) y \( \delta: \{1,2,3\}\times \{a,b\}\to \{1,2,3\} \).

¿Esta correcto?
"Haz de las Matemáticas tu pasión".

05 Enero, 2020, 05:39 am
Respuesta #7

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Muchas Gracias, entonces escrito formalmente el AFD es \( M=(K,\Sigma,\delta,s, F) \) en donde, \( K=\{1,2,3\} \), \( \Sigma=\{a,b\} \), \( s=1 \), \( F=\{2\} \) y \( \delta: \{1,2,3\}\times \{a,b\}\to \{1,2,3\} \).

¿Está correcto?

Está todo bien salvo que:

1) Si acordamos que todos los estados son finales tenemos que \( F=\{1,2,3\} \).

2) La función de transición \( \delta \), expresada así como la expresás no da cuenta de cómo se relacionan los estados. Hay que citar toda transición presente en el AFD, por ejemplo algunos elementos son: \( \delta=\{1\to a2,1\to b3,\ldots\} \).

Saludos