Consultas de Teórico

Buenas tardes :D

Según el libro de referencia del curso (Hopcroft, Motwani, Ullman):

En otro mensaje respondo lo de dos cintas. Cualquier cosa consultá :D

Sobre tus dudas de el autómata de dos cintas:

• a) ¿se empieza a consumir siempre del primer elemento del lado izquierdo?
  • No. Se puede empezar a consumir desde la cinta que ustedes quieran. De qué lado comiencen dependerá de las características de las relaciones entre una cinta y la otra. Por ejemplo, si el lenguaje a reconocer es $\{(a^k,a^pb^k): p>0 \wedge k>0\}$ va a convenir empezar del lado derecho porque cantidad p de a's no tiene relación con lo que está del otro lado de la cinta. Luego de consumir esas a's, se puede empezar a controlar que la cantidad de b's de la derecha es igual a la de las a's de la izquierda.
• b) para decir que consumí la totalidad de las 2 tiras, debo haber recorrido todos los elementos de ambas tiras y terminar en un estado final, pero tengo que ¿haber llegado a ese estado final consumiendo el último elemento de tira de la izquierda? O ¿puedo terminar posicionada en el último elemento de la derecha?
  • Ojo con el arranque de la pregunta. Uno puede decir que consumió la totalidad de las dos tiras y no llegar a un estado final. Es válido: es el caso en el que el par de tiras no es aceptado.
  • No existe una restricción sobre de qué lado leer el último símbolo. Puede que el último símbolo leído sea de la izquierda o de la derecha. Esto es igual tanto para el caso donde el último símbolo leído lleva a un estado final como para el caso donde no lo hace (lleva a un estado no final).
• c) ¿hay alguna forma de darme cuenta cuándo conviene moverme para un lado o para el otro?
  • Es difícil listar una serie de recetas para resolver los ejercicios, pero seguramente a medida que empieces a hacer varios vas a notar patrones.
    
  • En el ejemplo que puse en la respuesta de la pregunta a), podría haber primero arrancado por la izquierda y leer el primer símbolo, para luego consumir todas las a's del lado derecho hasta que consiga el símbolo "b" que corresponde al que leí en primer lugar de la cinta izquierda; luego seguiria consumiendo un símbolo de cada lado.
    
  • Otros ejemplos pueden ser cuando hay que controlar que un patrón se repite en un lado una cantidad múltiplo de las veces que aparece en el otro lado, como por ejemplo  $\{(a^{3k},b^k): k>0\}$. En ese caso vas a querer leer primero 3 a's del lado izquierdo para luego leer la b que le corresponde del lado derecho; o quizás hacer al revés: primero leer la b del lado derecho y luego buscar las 3 a's que corresponden del lado izquierdo.