Siguiente: Computaciones en máquinas de Un nivel arriba: Introducción a las máquinas Anterior: Introducción a las máquinas

Ejemplo: Cadenas equilibradas de paréntesis

Para tener una cadena equilibrada, cada ``)'' en ella ha de ``empatar'' con un correspondiente ``('' que lo anteceda. Para reconocer cadenas equilibradas, de manera general a cada ``('' ya empatado se le marcará por una A como ya revisado y a cada ``)'' se le marcará por una B. Procederemos como sigue:

1.

Inicialmente, se busca el primer ``)'', yendo de izquierda a derecha.

2.

Por cada ``)'',

(a)

se marca con B,

(b)

se busca hacia la izquierda el primer ``('' que lo empate,

(c)

si no se encontrare tal ``('' la cadena está desequilibrada. En otro caso, el ``('' se marca con A y se repite este ciclo.

3.

Si quedaren ``('' no empatados, la cadena está desequilibrada. En otro caso se tiene equilibrio y se termina el proceso.

El procedimiento queda descrito por la lista de quíntuplas mostrada en la tabla 1.4.

  

Table 1.4: Máquina de Turing para reconocer cadenas equilibradas de paréntesis.

Los cuatro estados de la máquina tienen una interpretación evidente:

$$\begin{eqnarray*}1 &:& \mbox{\rm avanza a la derecha buscando \lq\lq )'',} \\ 2 &:&... ...odo haya sido marcado,} \\ 4 &:& \mbox{\rm estado terminal.} \end{eqnarray*}$$

Como mero ejemplo veamos la computación correspondiente a una cadena dada. En cada instante, la casilla leída es la adyacente a la derecha del estado actual, el cual se escribe en negritas.

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert c\vert\vert}... ...m [S\'\i]}ABAABB\ \end{array} \\ \hline \hline \end{array}$$

El lector no debe de tener dificultad alguna en reconocer la lista completa de quíntuplas resultante del ejemplo, la cardinalidad del conjunto EA, producto cartesiano del conjunto de estados por el alfabeto, y la representación de la máquina como una lista de tercetas indicada por elementos en el conjunto EA.
Siguiente: Computaciones en máquinas de Un nivel arriba: Introducción a las máquinas Anterior: Introducción a las máquinas