junchan escribió:Hola,
Estoy con teoría de autómatas 2 y aún tengo unos días, alguien sabe alguna web donde haya teoría?
O si alguien tuviera la prueba de que si
A es REC => A* es REC
y
A y B son REC => A\B es REC
Sé que los REC están cerrados bajo diferencia y kleene y que los RE no. Pero necesito la prueba y no la encuentro por ningún lao.
He buscao en google y solo me salen pruebas de unión, concatenación, intersección...
Agradezco vuestra ayuda y no sé si esto va aquí O_0
PD: Si ponéis algún libro tb me vale
A lo mejor no tengo ni puta idea xq no me acuerdo muxo, pero... sabemos que todas las cadenas de A terminan en un estado final del automata de turing M. A* no debería, por fuerza, poder terminar tb siempre en un estado final de M? siendo asi tb REC.
Recuerdo que cada cadena de A esta contenida en A*, y cada cadena de A* esta formada a partir de cero, una o mas ocurrencias de cadenas de A.
Yo creo que con hacer reduccion al absurdo basta.
Cojemos y suponemos que A* no seria un lenguaje REC, alguna de sus cadenas no termina en un estado final de la máquina de turing M, pero como no va a terminar si ya hemos dixo que A lo es y todas terminan en un estado final de turing? xDD
![[discu]](/images/smilies/nuevos2/discutiendo.gif "discutiendo")
Pero como el cierre de A es infinito, hay cadenas para las que M(A) no para luego no es recursivo... ¿no? 
![[oki]](/images/smilies/net_thumbsup.gif "Ok!")
