19/09/2019, 08:04:04 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: AEF que reconozca cadenas que representen multiplos de 3 en binario  (Leído 6135 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« : 02/06/2010, 08:04:54 pm »

Hola, no se si alguien estudió teoría de autómatas pero matemáticamente también me vendría bien ayuda
Necesito construir como dice el título un Autómata de Estados Finitos que reconozca el lenguaje de las cadenas sobre el alfabeto {[texx]0,1[/texx]} que representen en binario múltiplos de 3.
Alguien conoce alguna característica de estas cadenas que me pueda servir?

Saludos
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #1 : 03/06/2010, 12:36:19 am »

No entiendo las expresiones que planteas, es algebra modular?
Podrías aclararme un poco
Desde ya muchas gracias por la respuesta
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.275

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #2 : 03/06/2010, 12:39:15 am »


En efecto, está tomando el módulo de la división por 2 del número 3.
Eso da un criterio de divisibilidad por 3, pero para números escritos en base 2.

En todo caso, lo que tienes que hacer es "usar" la propiedad que te muestra Topo en tu programa.

Y agrego unos comentarios.
Como lo que se obtiene al sumar digitos alternadamente es de nuevo un múltiplo de 3, basta repetir el proceso.
Una manera de garantizar que el proceso termina es observando que en cada paso del proceso el número obtenido es más pequeño que el anterior.
Se sigue así hasta alcanzar un número de una sola cifra, de ser necesario.

En línea

Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #3 : 03/06/2010, 12:49:56 am »

Ahi entendí la notación, el "_2" se refería a la base. Gracias
Para explicar un poco, un autómata de estados finitos es basicamente un grafo dirigido.
Cada nodo representa un estado y cada vector una función que toma un estado y un simbolo del alfabeto predefinido y devuelve un estado (que puede ser de aceptación o no)
Lo que haría el autómata que busco es que dada una cadena del [texx]\{0,1\}^*[/texx] (todas las concatenaciones de ceros y unos incluyendo la cadena vacía) la recorre y evalua en tiempo de recorrido (al ser de estado finito no tiene memoria) y cuando termina la cadena simplemente devuelve el estado en que concluyó.
Este puede ser de aceptación o no, lo que diría si la cadena está o no en el lenguaje que reconoce el autómata (en este caso multiplos de 3 escritos en binario)

PD: Como podría demostrar la propiedad que plantean?
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.275

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #4 : 03/06/2010, 12:54:04 am »

La máquina sólo recorre y lee?
¿Tiene permitido escribir sólo al final cuando arroja el resultado?
¿Tiene permitido volver atrás en la cadena de caracteres y leer de nuevo?
¿Tiene permitido escribir sobre las posiciones que va recorriendo, y luego retroceder y volver a leer alguna información?

¿Cómo reconoce el final de la cadena?
En línea

Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #5 : 03/06/2010, 01:16:14 am »

No, creo que estás tomando la idea de Maquina de Turing
El planteo de autómatas surge de intentar modelizar lenguajes. Se pueden clasificar en dos grandes modelos
Por Generadores y por Reconocedores
Los generadores serían las gramáticas, que definen un lengueja por reglas de producción. Formalmente son tuplas formadas por Terminales, no temrinales y reglas de producción
Es algo así como una forma de definición inductiva pero sólo se usa con el operador de concatenación, se subdividen en distintos tipos
Los reconocedores serían los autómatas, que definen un lenguaje por lo que reconocen sobre [texx]\sum^*[/texx] donde [texx]\sum[/texx] es el alfabeto
Un tipo de autómata es el conosido como autómata de estados finitos. Uno tiene una estado incial en donde se empieza situado e ingresa la cadena
Luego para cada simbolo del alfabeto hay una función desde ese estado inicial a otro estado (y desde este nuevo estado a otros o a sí mismo, y así se va armando un grafo).
Cuando le das una cadena lo que hace el autómata es comenzar en el estado incicial e ir moviendose según que simbolo va ingresando de un estado a otro (lee la cadena de a símbolos). Cuando la cadena termina (la cadenaa siempre es finita) es aceptada si el último estado al que llegó es de aceptación. De no ser de aceptación significa que la cadena no está en el lenguaje que se define con ese autómata
Hay varios temas que omití bastante interesantes. En si, toda esta teoría es muy interesante. Se demuestra entre otras cosas que existen lenguajes que no se pueden generar ni reconocer, y varias cosas más en el medio. Si les interesa el tema se los recomiendo, a mi me ha gustado y aún no di mucho.
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.275

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #6 : 03/06/2010, 01:39:19 am »

Bueno, pero entonces ¿qué es lo que puedo hacer mientras avanzo por la cadena?
¿Tengo solo un bit de estado que me dice "Aceptado/No aceptado"?
En línea

topo23
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Argentina Argentina

Mensajes: 940


Ver Perfil
« Respuesta #7 : 03/06/2010, 03:40:42 am »

..
En línea

.
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.275

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #8 : 03/06/2010, 01:44:36 pm »

Ahora entiendo. Está muy claro.

Los estados serían (0, 1), (0, -1), (1, 1), (1, -1), (2, 1), (2, -1).

El proceso comienza en (0, 1), por ejemplo, que indicaría que el estado inicial es "resto 0 al dividir por 3, y la próxima alternancia a realizar en la suma debe tener signo positivo".

Si encuentro un 0 en el siguiente dígito, el estado no cambia.
Si encuentro un 1, entonces los cambios de estado serian como sigue:

(0, +1) ---> (1, -1)
(0, -1) ---> (2, +1)
(1, +1) ---> (2, -1)
(1, -1) ---> (0, +1)
(2, +1) ---> (0, -1)
(2, -1) ---> (1, +1)

¿Estará bien el grafo así planteado?

Muy lindo este tema.

Saludos
En línea

Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #9 : 03/06/2010, 02:40:35 pm »



Por ejemplo un automata que decide si la suma de los digito de una cadena binaria es multiplo de 2 seria el siguiente:
Estados: A y B
* Si estamos en A y nos llega un 0 nos quedamos en A.
* Si estamos en A y nos llega un 1 nos movemos a B.
* Si estamos en B y nos llega un 0 nos quedamos en B.
* Si estamos en B y nos llega un 1 nos movemos a A.
Si al terminar estamos en A la suma de los digitos es par.

Con ese autómata la cadena vacía sería aceptada, pero no tiene dígitos que sumar. Eso supongo que se decide con una convención que uno aclare. Para no aceptar la cadena vacía (a mi criterio no debería estar en el lenguaje) debes agregar un estado inicial distinto de A y B y razonar de la misma manera en lo que seguiría


Si encuentro un 0 en el siguiente dígito, el estado no cambia.

No exactamente, porque cambiaría la alternancia de suma o resta
Si ingresaras un 0 serían estas transiciones

(0, +1) ---> (0, -1)
(0, -1) ---> (0, +1)
(1, +1) ---> (1, -1)
(1, -1) ---> (1, +1)
(2, +1) ---> (2, -1)
(2, -1) ---> (2, +1)

Logré armar el autómata con 9 estados, agrego a lo que ustedes colocaron un estado inicial, en el cual me paro antes de ingresar cualquier cadena (en cual indicaría el estado de la cadena vacía que no acepto en el lenguaje)
Luego si el número comienza con 0 voy a un estado que si la cadena sigue sólo con ceros se queda allí, y si ingresa un 1 cae en otro estado de no aceptación del que no sale (simplemente hago que al ingreso de un 0 o 1 siga en ese estado)
Si el primer símbolo es un 1 hago el razonamiento que hiciste con la corrección que te mencioné cuando ingresas un 0 (quizás me haya equivocado aunque creo que digo bien)


Ahora, me quedó la dude de cómo se demuestra la propiedad de que la suma alternada es múltiplo de 3. Debería preguntarlo en la sección "Teoría de Números"?

Saludos

PD: Si quieren preguntar sobre autómatas no tengo problema en que me envíen mensajes, les puedo recomendar el libro "Teoria de la Computacion-Lenguajes formales automatas y complejidad" (J. Glenn Brookshear) No es un libro demaciado detallista pero abarca bastantes temas.
En línea
Leusss
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 315


Ver Perfil
« Respuesta #10 : 03/06/2010, 02:56:24 pm »

Estado inicial: [texx]S[/texx]

Estados: [texx]S, P_0, P_1, P_2, I_0, I_1, I_2[/texx]

Estados aceptados: [texx]P_0, I_0[/texx]
[texx]f(S,0)=I_0[/texx]
[texx]f(S,1)=I_1[/texx]
[texx]f(I_0,1)=P_2[/texx]
[texx]f(I_0,0)=P_0[/texx]
[texx]f(I_1,0)=P_1[/texx]
[texx]f(I_1,1)=P_0[/texx]
[texx]f(I_2,0)=P_2[/texx]
[texx]f(I_2,1)=P_1[/texx]
[texx]f(P_0,0)=I_0[/texx]
[texx]f(P_0,1)=I_1[/texx]
[texx]f(P_1,0)=I_1[/texx]
[texx]f(P_1,1)=I_2[/texx]
[texx]f(P_2,0)=I_2[/texx]
[texx]f(P_2,1)=I_0[/texx]
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.275

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #11 : 03/06/2010, 06:11:28 pm »

Es cierto, me equivoqué al decir que cuando hay un 0 el estado no cambia.

Porque sí cambia.


No entiendo por qué tendrías que tener 9 estados.
Los 6 estados que sugirió Topo me parecen bien. (Aunque la verdad, estoy aprendiendo con ustedes sobre este tema, no sé cómo va la cosa).

No sé cómo se arreglan este tipo de cosas.
Pero si tu problema dice: "dada una cadena de digitos binarios bla bla",  lo cierto es que la cadena vacía no es una cadena de digitos binarios, porque no representa número alguno.

Así que no hay cadena vacía.




En cuanto a la cuestión de ser multiplo de 3, eso es teoría de números, pero no hace falta abrir un debate nuevo sobre el tema.

La cuestión es que la suma, la resta y la multiplicáción "módulo" un número, se conservan a ambos miembros.
O sea, si sumo números de un lado y les tomo el resto de la división por b, del otro lado obtengo la suma de los restos de la división por b.
Si multiplico o elevo a potencia un número y le tomo el resto al dividir por b, es lo mismo que si tomo el resto del número y lo multiplico o lo elevo a la potencia.

Las operaciones se conservan al tomar restos, y por eso hay una teoría de congruencias.

Cuando tomás un número como 315, en base 10, y querés saber si es múltiplo de 7, hacés la descomposición en base 10 y le tomás los módulos de dividir por 7. Usando que el resto de 10 / 7 es 3, se puede reemplazar el 10 por el 3, y queda la congruencia:

[texx]3 * 10^2+1*10^1+5\equiv_7 3*3^2+1*3^1+5=35[/texx]

O sea, 315 y 35 tienen el mismo resto al dividir por 7.
Pero seguimos un paso más:

[texx]35=3*10^1+5\equiv_7 3*3^1+5=14[/texx]

O sea, 35 y 14 tienen el mismo resto módulo 7. Y otro paso:

[texx]14=1*10^1+4\equiv_7 1*3^1+4=7[/texx]

que obviamente es múltiplo de 7...

Ahora, con base 2, se usa que [texx]2\equiv_3 -1[/texx], y por lo tanto [texx]2^n\equiv_3 (-1)^n[/texx], y de ahí la alternancia.

Saludos
En línea

Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #12 : 03/06/2010, 07:24:56 pm »

Ah, ahi entendí. Muy buena la explicación, gracias

Por lo de los 9 estados tomo los seis de topo y agrego estos:
1 estado inicial que no es de aceptación (en su caso partían de (0,1) y eso ocacionaba que al ingresar la cadena vacía sea aceptada)
Luego los otros dos estados son por una convención que tomé yo sobre que si el número no empieza con 1 debe ser cero unicamente (o sea, tomo que 3 es igual a 11 y que si ingresan 011, 0011, 0[texx]\ldots[/texx]011 los considero distintos del 3 , pero eso fue algo mío)

Si quito los dos estados que tomé por mi convención se llega a armar con 7 estados. El que agregúe como el inicial (el estado inicial debe ser único) es una correción para que no acepte la cadena vacía.
Creo que lo que armó wolfking2 es lo que quedaría con los 7 estados que mencionó

Saludos
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!