Credit image

¿Te gusta el diseño web? ¡Echa un vistazo a la documentación de LenguajeCSS.com!

Esquemas de TALF: Teoría de Autómatas y Lenguajes formales

¡OJO! Probablemente, este artículo no interese a lectores que no cursen una Ingeniería informática.

Este año en la asignatura de Teoría de Autómatas y Lenguajes formales he aprendido bastante sobre Autómatas finitos deterministas (DFA), Autómatas finitos no deterministas (NFA), Autómatas a pilas (PDA), Máquinas de Turing (MT) y otros.

Reorganizando apuntes y demás, he diseñado unos pequeños esquemas que aunque no bastan para estudiar con ellos la asignatura, si que pueden servir de ayuda a compañeros que cursen la asignatura (o futuros alumnos que lleguen hasta esta página).

Aún falta el tema de resolubilidad y el resto puede que contenga alguna errata, pero para usar de guía creo que sirven bastante bien.

Escrito por Manz, el , en ingenieria. Comentarios recibidos: 24.

24 comentarios de lectores
Viktor
Viktor
1

Esa asignatura la aprobé el año pasado n_n, aunque en la universidad de Zaragoza se llama Lenguajes, Gramaticas y Automatas (LGA). Aquí es de las asignaturas con menos temario, ¿allí también es tan corto?

Manz
Manz
2

Hombre, el temario creo que no es demasiado extenso (de hecho son sólo 4 temas), pero según compañeros de cursos posteriores es de las más duras de la carrera.

Paco
Paco
3

Gran asignatura TALF, es la tipica asignatura que presenta realmente retos, sobre todo para sacar la ¿gramatica? (no recuerdo los nombre bien). En la autonoma de Madrid donde la estudié era bastante durita, pero merecia la pena.

jose
jose
4

En Cádiz no es de las más duras de la carrera, aunque de las optativas sí es una de las que tiene más chicha, junto con concurrente. El año pasado por desgracia nos perdimos mucho en la dinámica de "teorema - demostración - corolario - teorema - demostración - teorema - demostración - corolario1 - corolario2 - ..." y no llegamos a la parte interesante de computabilidad, problemas NP-completos y demás. Nos quedamos en máquinas de Turing. Junto con traductores, que al principio va de lo mismo, una de las más atractivas de mi carrera, por lo diferente (y sobre todo si las comparamos con rollazos infumables como Ingeniería del software )

jose
jose
5

Ey, es raro que hayas incluido el algoritmo CYK pero no el de Early. ¿te cae mal?

Abel
Abel
6

Te has tardado mucho Manz, la materia ya la acabo de pasar y con mucha batalla, estudio Ingenieria en Sistemas Informaticos en Mexico y aunque la materia en mi carrera se llama Teoria de la Computacion, es identica a la tuya.

ZiRRuS
ZiRRuS
7

Aquí en Murcia se llama igual que por ahí, y esta en segundo de carrera. Hace ya unos añitos que la pasé, pero te aseguro que aquí esa asignatura es hueso, de las duras vamos. Forma parte de ese conjunto de asignaturas que pueden atragantarse en segundo de carrera ;) Recuerdo que un buen libro era uno de un tal Isasi. Nos vemos!

ReMaTxEs
ReMaTxEs
8

En la UPSA se cursa en 3º de Carrera, y la verda aunque tiene cierto intríngulis a mi al menos me pareció interesante... Sobre todo las practicas con los Diagramas en Escalera y un autómata de (No m acuerdo, xo era Japo xD) , y otro programita que funcionaba poniendole un adaptador(Mochila) en el Puerto Paralelo y hacia simulaciones de autómatas industriales...

Niiko
Niiko
9

En la universidad de Málaga esa asignatura es anual, no es de las más complicada pero si es un coñazo de aburrida y larga.

Javi Moya
Javi Moya
10

esta asignatura cuando yo la hice tenia dos partes... I y II... la parte I saquè matricula de honor ! :D pero en la segunda parte... con una profe que no tenía ni idea pasé de ir a clase.... y la dejé para el verano... y me costó aprobarla!!

bline
bline
11

Realmente ahora no me interesa para nada, no obstante.. creo k me lo guardaré pal proximo año cuando, si la nota me da, entre en la ull xD

Nadie en especial
Nadie en especial
12

Útil, útil ^_^

Fabio Andres P
Fabio Andres P
13

En la universidad del Magdalena, dan esa materia, es de las mas cheveres y tenemos un grupo de estudio de TALF, llamado TALF-Colombia.

Rubisco
Rubisco
14

Estos apuntes son escuetos pero muy útiles, repito, son escuetos pero muy útiles. De hecho, de hecho, me han hecho recordar muchas cosas de la asignatura.

carlinho
carlinho
15

En italia se llama Informatica teorica 1 y 2, estoy aqui de erasmus y esta asignatura me está costando la vida. Vamos a ver si tus esquemas me hacen la vida un poco mas facil, porque con los apuntes en italiano no me estoy enterando de na! Muchas gracias por colgarlos

jordi
jordi
16

¿Y alguien puede resumir la utilidad de todo esto en la vida real?

Manz
Manz
17

@jordi: pues para empezar, la comodidad de simplificación y potencia (en programación) del uso de las expresiones regulares.

jordi
jordi
18

Pues yo nunca he entendido la relación que hay entre el modelo teórico y las expresiones regulares de los lenguajes de programación reales. Según la teoría, sólo son expresiones regulares el conjunto vacío, la palabra sin símbolos, a, b, a + b y todo lo que se derive de esto. Es decir, que la expresión regular teórica describe un lenguaje mucho más sencillo que el que describe qualquier combinación de símbolos de una expresión regular práctica y real, como las que hay en el enlace que adjuntas. Entonces, ¿cómo sería el DFA que describe una expresión regular de PHP? ¿Puede construirse con la teoría que conocemos? ¿Hay realmente alguna relación, como pregunto al principio de mi mensaje, entre las expresiones regulares teóricas y las reales? En cualquier caso, ¿qué nos importa a nosotros? ¿A dónde vamos? ¿De dónde venimos? ;-) Gracias y saludos!

Manz
Manz
19

@jordi: hombre, tienes que darte cuenta que la teoría de autómatas y lenguajes formales que se estudia en las ingenierías es en cierta forma una base (concatenación, cierre, etc...). Podría estudiarse a nivel teórico muchas más cosas (por ejemplo, las anclas u cualquier otra del POSIX extendido), pero eso sería cuestión de profundizar si te interesa el tema. Respecto a tus preguntas, date cuenta que no sólo existen los DFA, sino también los NFA, PDA, Autómatas sensibles al contexto, Máquinas de Turing, etc... Al fin y al cabo, yo pienso que todo esto sirve como inicio para profundizar y, si es de tu interés, conocer la base para aprender y dedicarte a investigar (y quizás encontrar nuevos caminos). Si te interesa el tema, te puedo recomendar un libro que tengo y me gustó bastante: Mastering Regular Expressions de O'Reilly. ¡La correspondencia existe! ¡Y a veces duele!

Francisco
Francisco
20

Hola, Como dicen varios de mis compatriotas en México se le titula Teoria de la Computacion. Es Interesante, corta y super util la materia. Recomiendo mucho cursarla a la par de Sistemas Digitales o Programacion de Chips, Pics, Etc. Gracias por el aporte. Justo antes de mis Parciales.!!! Genial!!!

alexander
alexander
21

En la unisimon de Barranquilla colombia se llama teoria de compiladores los temas son basico expresiones regulares, automatas finitos (afd afn) y terminamos programando un analizador sintactico, no se en otrs partes pero esta materia es de las mas dificiles

Andrea
Andrea
22

Las maquinas de turing, ¿En que forma son aplicables a la vida real?

Dani
Dani
23

Aquí dejo un blog de automatas, gramáticas y lenguajes formales que estamos creando, alomejor os puede interesar: Automatas finitos deterministas Automatas finitos no deterministas Lenguajes formales Gramáticas Un saludo, iremos actualizando poco a poco

  • 2
Javier
Javier
24

Aquí podreís encontrar todo tipo de información acerca de,automatas finitos , gramaticas y lenguajes formales Un saludo

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.