Page 116 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

116

d (q1, <) = (q1, <, R)

d (q1, a) = (q1, b, R)

d (q1, b) = (q1, a, R)

d (q1, >) = (q1, >, S), donde S significa "permanecer", es decir no mover la cabeza de
lectura/escritura. Este ALA complementa sus cadenas de entrada convirtiendo las a’s en b’s y
viceversa.

CARACTERÍSTICAS

• Dada una cadena x en la cinta de entrada si el ALA lee toda la cadena y:

Termina en el estado final→ cadena aceptada

Termina en el estado no final→ cadena rechazada

• En ninguna cinta se permite δ (#, L) ni δ ($, R), o sea no se puede ir más allá de los
símbolos que delimitan la cinta ni

ESTRUCTURA

EXCLUSIONES

• Lenguajes producidos por una gramática de Tipo 0, lenguajes sin restricciones.

• Lenguajes recursivamente numerables, los cuales sólo son reconocidos por las máquinas
de Turing.

APLICACIONES

En el caso de las computadoras, estos dispositivos cuentan con un rasgo de seguridad, los cuales
indican la capacidad de almacenamiento de las mismas, por lo que no se debe de sobrepasar su
límite. Los autómatas linealmente acotados se restringen a un área limitada por una constante,
esto es similar con un ambiente de programación donde se limitan los tamaños de valores para las
variables. El problema de detenimiento es solucionado para el autómata linealmente acotado.