Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[AYUDA] TP Discreta/Algoritmos: Programar un automata
Autor Mensaje
Nico12 Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 35
Agradecimientos dados: 27
Agradecimientos: 11 en 2 posts
Registro en: Dec 2015
Mensaje: #1
[AYUDA] TP Discreta/Algoritmos: Programar un automata Dudas y recomendaciones Algoritmos y Estructuras de Datos y 1 más
Hola!
Creo que este es el primer año del trabajo practico en conjunto de algoritmos y discreta, y, como creo que pasa con la mayoria de los tps, no se puede hacer algo hasta que no lo hayan explicado, y se te termina juntando con los parciales/finales. A mi y a mi grupo nos gustaria poder ir haciendo el tp ahora para no andar justos de tiempo, pero como todavia no vimos los temas se complica. La cuestion es que mi profesor de Algoritmos me dijo que programar un automata no es algo que se vea en clase. Por lo que no entiendo concretamente que es lo que pide el enunciado de un punto de la Seccion 4 del tp. Se que Teoria de Automatas es un tema de discreta, pero me parece que es el ultimo de todos, y esta semana recien vimos induccion por lo que creo que hasta el ultimo par de semanas antes de la entrega no lo van a haber explicado, y en algoritmos ya se que no se va a ver.
El tp pide lo siguiente:
"Programar un autómata reconocedor de contraseñas, indicando los estados por lo que pasó
y si la contraseña indicada es válida o no. Documentar la estructura de la contraseña usada
mediante expresión regular o gramática."

Estaria muy agradecido si alguien me pudiera iluminar un poco respecto de que es lo que esta pidiendo.

Gracias!
30-08-2016 20:06
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Imakuni Sin conexión
Presidente del CEIT
Boxes tastes like mush
********

Ing. en Sistemas
Facultad Regional Córdoba

Mensajes: 7.006
Agradecimientos dados: 116
Agradecimientos: 124 en 82 posts
Registro en: Jul 2008
Mensaje: #2
RE: [AYUDA] TP Discreta/Algoritmos: Programar un automata
1 - Me parece cualquiera. Si bien es un tema de discreta, se profundiza mucho más en Sintaxis. Y en esa materia ves tambien expresiones regulares.

2 - No se quien sera jefe de catedra de sintaxis. En mi epoca vendian unos apuntes que te ponian el codigo de un automata, hecho en C.

3 - Automatas es el ultimo tema, pero no tiene mucha relación con los demás (bueno, podes considerarlo un digrafo si queres =P).

Para que te ayudes con google, lo que te piden es hacer un Automata Finito.

Mirate estos videos:

https://www.youtube.com/watch?v=P0AxQvJcN2Q
https://www.youtube.com/watch?v=8KKFcHpU0w0

Si el primero te parece que no entendes un pomo, mirate el segundo que te da un ejemplo.


Despues, no queda otra que ponerse a leer. La verdad me parece cualquiera que les den esto, es un tema ultra copado para verlo de manera formal.
(Este mensaje fue modificado por última vez en: 30-08-2016 20:37 por Imakuni.)
30-08-2016 20:32
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] Imakuni recibio 2 Gracias por este post
Nico12 (30-08-2016), missmetal (31-08-2016)
Nico12 Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 35
Agradecimientos dados: 27
Agradecimientos: 11 en 2 posts
Registro en: Dec 2015
Mensaje: #3
RE: [AYUDA] TP Discreta/Algoritmos: Programar un automata
Muchas gracias!
30-08-2016 21:40
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Nico12 Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 35
Agradecimientos dados: 27
Agradecimientos: 11 en 2 posts
Registro en: Dec 2015
Mensaje: #4
RE: [AYUDA] TP Discreta/Algoritmos: Programar un automata
Perdon, pero todavia me quedaron dos dudas:

Si hago un automata finito que actue, por ejemplo, asi:
Empieza en un estado 0, y recibe una cadena de caracteres.
Evalua caracter a caracter, y si son letras mayusculas o minusculas no hace nada. Pero si encuentra un caracter que no sea una letra y esta en el estado 0, cambia al estado 1.
El estado de aceptacion seria 0, los estados posibles 0 y 1. El alfabeto todos los caracteres.
Y las contrasenas que toma serian las que contienen solo letras(el lenguaje creo que se dice).

Les parece que cumpliria con lo pedido?

Lo que todavia no entiendo nada es que seria la "expresion regular" o "gramatica".
31-08-2016 20:18
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Imakuni Sin conexión
Presidente del CEIT
Boxes tastes like mush
********

Ing. en Sistemas
Facultad Regional Córdoba

Mensajes: 7.006
Agradecimientos dados: 116
Agradecimientos: 124 en 82 posts
Registro en: Jul 2008
Mensaje: #5
RE: [AYUDA] TP Discreta/Algoritmos: Programar un automata
Esta casi-bien.

No existe el "no hace nada". Cada letra que reciba el automata, si o si tiene que pasar por una transición.
El truco está en hacer una transición cuyo estado inicial sea igual al estado final, así "se queda" en el mismo estado.

Lo demas está bien. Si tu password solo acepta letras, y dejas afuera todos los demas caracteres, si, tendrias un AFD de dos estados.

Desconozco si la consigna que te dieron es más amplia. Tu automata, por ejemplo, tambien estaría aceptando la cadena vacia (o sea, que no haya ingresado nada). Tendrias que preguntarle al profesor que tipo de password quiere, y a partir de ahi hacer el automata.


Ahora, terminologia (masomenos, hace mil la cursé):
- El alfabeto es un conjunto de simbolos. No more, no less.
* Si, un alfabeto es un conjunto de simbolos. Conjunto matematico. Ej: {a,b,c,d,1,4}
- Una cadena es una tupla de simbolos.
- Un lenguaje, es un conjunto de "cadenas", y un alfabeto.
* O sea, es una 2-upla (Alfabeto, Cadenas). Ej: ({a,v,c},{(v,a,c,a),(c,a,v,a),(v,a)}).

- Una gramatica, es una forma de definir un lenguaje, sin tener que enumerar todas las combinacion de cadenas.
* Ver: https://es.wikipedia.org/wiki/Gram%C3%A1tica_formal

- Un automata, es una forma de definir un lenguaje, sin tener que enumerar todas las combinaciones de cadenas.
* Si. Gramatica y Automata sirven para los mismo. Solo que su mecanismo es distinto, pero se puede pasar de una gramatica a un automata y viceversa.
* Leete esto: http://www.exa.unicen.edu.ar/catedras/cc...eGRyER.pdf . En la pagina 2 te pone el algoritmo para pasar de automata finito deterministico a gramatica regular.

- Una expresion regular, es una forma de definir ciertos lenguajes, sin tener que enumerar todas las combinaciones de cadenas.
* Casi es igual, una expresion regular solo sirve para lenguajes del tipo 3, que OH casualidad, son los que generan los automatas finitos deterministicos.
* Lo mejor aca es ponerte a ver si el libro de discreta ahora lo explica. Estaria bueno si te dicen que clase de "expresiones regulares" quieren si no está en el libro. En sintaxis veiamos expresiones regulares, y expresiones regulares extendidas. En la vida real, se utilizan expresiones regulares con muchas mas cosas copadas. Si te pones a googlear, probablemente encuentres definiciones de esta ultima.
(Este mensaje fue modificado por última vez en: 01-09-2016 01:05 por Imakuni.)
01-09-2016 01:04
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Nico12 Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 35
Agradecimientos dados: 27
Agradecimientos: 11 en 2 posts
Registro en: Dec 2015
Mensaje: #6
RE: [AYUDA] TP Discreta/Algoritmos: Programar un automata
Muchisimas gracias!

Saque de la biblioteca el libro "automatas finitos y expresiones regulares" de Muchnik y leyendolo arme la expresion regular(que creo que esta bien. Al final cambie el automata a uno que solo acepta cadenas de 3 letras mayus/minus(para hacer mas sencilla la expresion regular). La expresion regular me quedo:

Expresion regular:
((a+b+c+...+z)+(A+B+C+...+Z)).((a+b+c+...+z)+(A+B+C+...+Z)).((a+b+c+...+z)+(A+B+C+...+Z))

El simbolo . representa la concatenacion de caracteres y el + el O(son los simbolos con los que explicaba el libro).

Trate de armar la gramatica y me esta quedando algo asi:
Spoiler: Mostrar
0 -> a1
0 -> b1
0 -> c1
.
.
.
0 -> z1
0 -> A1
0 -> B1
0 -> C1
.
.
.
0 -> Z1

1 -> a2
1 -> b2
1 -> c2
.
.
.
1 -> z2
1 -> A2
1 -> B2
1 -> C2
.
.
.
1 -> Z2

2 -> a3
2 -> b3
2 -> c3
.
.
.
2 -> z3
2 -> A3
2 -> B3
2 -> C3
.
.
.
2 -> Z3
(Este mensaje fue modificado por última vez en: 01-09-2016 21:30 por Nico12.)
01-09-2016 20:49
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.