Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llaman lenguajes recursivos. Un posible alfabeto sería, digamos, {a, b} , y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba, las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b. Se caracterizan porque para cada uno de ellos existe una máquina de Turing que aceptará cualquier palabra del lenguaje y parará siempre.
A continuación algunos ejemplos que yo invente:
L = {0, 1}*
A -> 0A | 1A | E (vació)
Para:
101101
A
1A
10A
101A
1011A
10110A
101101A
101101E
Resultado = 101101
Otro ejemplo:
L = { j , a }
B -> j B a | BB | E (vació)
Para:
j j j a j a a a
j B a
j j B a a
j j B B a a
j j j B a B a a
j j j E a B a a
Resultado = j j j a j a a a
Todo consiste en sustituir por las opciones que te brinda el lenguaje para formar la frase para llegar al resultado, bueno eso es todo, espero y les pueda servir.
Fuente: http://www.mitecnologico.com/Main/LenguajesDecidibles
esta muy padre tu ejemplo le entendi mejor a lo de la maquina turnig ahora bien me toca a mi hacer el ejemplo gracias me has aportado ideas *-*
ResponderEliminar(:
Gracias!, te deseo éxito en tus ejemplos y que bueno que te sirvió la entrada :)
ResponderEliminarJe, tus ejemplos son mis ejemplos con cambio de alfabeto :P Te pongo 4 puntos por la sesión 3 por esta entrada. A Karen no le entiendo nada ya que tus ejemplos no se tratan sobre máquinas Turing ;)
ResponderEliminar