UTNianos

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!

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 ).

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.

Muchas gracias!

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".

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.

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: