Page 105 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

105

ENTREGA XII

AUTOMATAS LINEALMENTE ACOTADOS – NATURALEZA DECIDIBLE –
LENGUAJES RECURSIVAMENTE ENUMERABLES Y LOS RECURSIVOS.
En 1964 Sige-Yuki Kuroda descubre que los lenguajes de tipo 1 son reconocidos por los
autómatas linealmente acotados. Los autómatas linealmente acotados son similares a una MT,
pero con menos capacidad.

“ un autómata linealmente acotado es una máquina de Turing cuya cinta está formada solamente
por celdas de kn de largo, donde la longitud n es la secuencia de la entrada y k es una constante
asociada al autómata linealmente-acotado particular, es decir la cantidad de cinta que el autómata
permite usar se limita por un factor lineal k para que cuando entre una palabra de tamaño n (los
símbolos de n) , la máquina determine si la palabra es aceptable, o si la palabra está en el lenguaje
del autómata…”

Estos solo leen un tamaño de cinta definido por un rango descrito entre los símbolos #, $. Este
tipo de lenguajes, que aceptan estos autómatas, son denominados sensibles al contexto y por lo
general son de naturaleza decidibles.

Entendamos por decidibles:

Aquellos que siempre pararan, aceptando o rechazando, la cadena de entrada. Es decir, hay una
solución para “el problema”. Este tipo de problema evidentemente tiene resuelto el problema de
la parada; es decir son problemas de naturaleza computable. Es decir, son enumerarles, o
numerables.

Al definir como numerables, significa que leyendo uno a uno los símbolos de la entrada no hay
bucle en el que la máquina cae, sino que esta llega a un estado de parada que puede ser aceptar o
rechazar, pero decide, hay solución, decisión total siempre, estos también se les llama recursivos.
A estos también se les llama recursivos, pero estos, a su vez son un subconjunto de los
recursivamente enumerarles, los recursivamente enumerarles, (el conjunto universal), contemplan
lenguajes para los cuales pueda que entrando en un bucle encuentren o no solución, o sea se les
asocia una solución parcial, una decisión parcial, si finalmente resuelven y paran aceptando, o
simplemente se “queda”; así mismo un problema del tipo recursivamente enumerarle, puede caer
en un bucle y al final decide.

Existe una relación entre lenguajes recursivos y recursivamente enumerarles. Los recursivos es
un subconjunto de los recursivamente enumerarles. Básicamente, un lenguaje recursivo es aquel
para el que existe un ámbito total de decisión; y una definición de lenguajes enumerarles
recursivamente es aquel para el que existe una decisión parcial; es decir, una máquina de Turing
que, dando como entrada una palabra sobre su alfabeto, aceptará o rechazará correctamente la
palabra de acuerdo con su idioma, o si la palabra no está en su idioma, puede repetir para siempre,
(no para) no tiene resuelto el problema de la parada.

“Se podría decir que Turing, cuando inventó su máquina, inventó también los lenguajes formales,
ya que esta desde el principio fue concebida como un dispositivo que operaba sobre cadenas de
símbolos dispuestos sobre una cinta. Pero Turing hizo algo más que «inventar» los lenguajes
formales, descubrió que dentro del universo que estos ocupan, hay algunos lenguajes muy
especiales que quedan fuera de la galaxia de lenguajes interesantes definida por las capacidades
computacionales de la máquina de Turing.