Page 114 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

114

Ejemplo 2:

Este programa comprueba si los paréntesis '(', ')' en una cadena están equilibrados.
Entrada: una cadena que contiene (y) pero no espacios en blanco o '!'
El programa realiza un seguimiento del número de '(' encontrado en una pila a la izquierda de la cinta.
Cuando se lee un nuevo '(', se empuja un '(' adicional a la pila. Cuando se lee un ')', aparece un '('.
Si los paréntesis están equilibrados, la pila debe estar vacía cuando se alcanza el final de la entrada.

; Set up stack
0 * * l 1
1 _ ! r 51

; Find first non-blank
5 _ _ r 5
5 * * * 10

; Find first ( or )
10 ( ! l 20
10 ) ! l 30
10 _ _ l 40
10 * ! r 10

; Push ( onto stack
20 ! ! l 20
20 * * * 21
21 _ ( r 50
21 * * l 21

; Pop ( from stack
30 ! ! l 30
30 * * * 31
31 _ _ r 32
31 * * l 31
32 ( _ r 50
32 ! ! * 80 ; Trying to decrement below 0, unbalanced parentheses, missing (

; Reached end-of-input, check if stack is empty
40 ! ! l 40
40 _ _ r 60 ; Stack is empty, parentheses are balanced
40 * * l 70 ; Stack is not empty, unbalanced parentheses, missing )

; Finished increment/decrement, return to start
50 ! ! r 51
50 _ _ l 40 ; Reached end-of-input
50 * * r 50
51 ! ! r 51
51 * * * 10

; Parentheses balanced
60 ! _ r 60
60 * * * accept

; Parentheses unbalanced - missing )
70 _ _ r 71
70 * * l 70
71 _ * * reject
71 * _ r 71

; Parentheses unbalanced - missing (
80 _ * * reject
80 * _ r 80

accept * : r accept2
accept2 * ) * halt-accept

reject * : r reject2
reject2 * ( * halt-reject

Initial input: 12(2+(3^(4-1))) -> aceptado en 217 pasos 
Initial input: 4(5+3))) -> rechazado en 54 pasos 

Referencias:
http://morphett.info/turing/turing.html