ingenieria
24

Escrito por

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

RELACIONADOS Introducción a las expresiones regulares RELACIONADOS Las máquinas que aprendieron a pensar RELACIONADOS El método Simplex Revisado
x Introducción a las expresiones regulares
Manz

24 comentarios

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

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

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

Publica tu opinión