Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba .
Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que , por ejemplo
La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.
No hay comentarios:
Publicar un comentario