teoria

DETERMINISMO E INDETERMINISMO 49
3.3 Determinismo e Indeterminismo
3.3.1 El Automata como Programa
Una manera bastante natural de interpretar el automata nito es usar un pseudo{
codigo para expresar un automata como un programa con un while basado en el
sistema de transicion anterior. Informalmente, sea A := (Q; ; q0; F; ) un automata.
El programa (algoritmo) que dene es el dadopor la siguiente descripcion:
Input: x 2 

(una palabra sobre el alfabeto).
Initialize: I := (q0; x) (la conguracion inicial sobre x)
while I 62 F  fg do
if I = (q; x1x
0
), x1 2  [ fg, x1x
0 6= , then I := ((q; x1); x0
)
else Ouput NO

od
Output YES
Notese que hemos introducido deliberadamente un pseudo{codigo que no necesariamente termina en todos los inputs. Esto espor analoga con las maquinas de
Turing y el estudio de los lenguajes recursivamente enumerables y recursivos. Aqu,
el pseudo{codigo tiene una interpretacion directa y natural en el caso determinstico
y genera una forma imprecisa en el caso indeterminstico. Esta interpretacion como
programa (determinstico) de este pseudo{codigo depende esencialmente de la ausencia de dosobstrucciones:
 La presencia de transiciones, esto es, de transiciones de la forma (q; ) que
pueden hacer que caigamos en un ciclo innito.
 La indenicion de I = ((q; x1); x0
) por no e



DETERMINISMO E INDETERMINISMO 49
3.3 Determinismo e Indeterminismo
3.3.1 El Automata como Programa
Una manera bastante natural de interpretar el automata nito es usar un pseudo{
codigo paraexpresar un automata como un programa con un while basado en el
sistema de transicion anterior. Informalmente, sea A := (Q; ; q0; F; ) un automata.
El programa (algoritmo) que dene es el dado por la siguiente descripcion:
Input: x 2 

(una palabra sobre el alfabeto).
Initialize: I := (q0; x) (la conguracion inicial sobre x)
while I 62 F  fg do
if I = (q; x1x
0
), x1 2  [ fg,x1x
0 6= , then I := ((q; x1); x0
)
else Ouput NO

od
Output YES
Notese que hemos introducido deliberadamente un pseudo{codigo que no necesariamente termina en todos los inputs. Esto es por analoga con las maquinas de
Turing y el estudio de los lenguajes recursivamente enumerables y recursivos. Aqu,
el pseudo{codigo tiene una interpretacion directa y natural en el casodeterminstico
y genera una forma imprecisa en el caso indeterminstico. Esta interpretacion como
programa (determinstico) de este pseudo{codigo depende esencialmente de la ausencia de dos obstrucciones:
 La presencia de transiciones, esto es, de transiciones de la forma (q; ) que
pueden hacer que caigamos en un ciclo innito.
 La indenicion de I = ((q; x1); x0
) por no e
DETERMINISMOE INDETERMINISMO 49
3.3 Determinismo e Indeterminismo
3.3.1 El Automata como Programa
Una manera bastante natural de interpretar el automata nito es usar un pseudo{
codigo para expresar un automata como un programa con un while basado en el
sistema de transicion anterior. Informalmente, sea A := (Q; ; q0; F; ) un automata.
El programa (algoritmo) que dene es el dado por lasiguiente descripcion:
Input: x 2 

(una palabra sobre el alfabeto).
Initialize: I := (q0; x) (la conguracion inicial sobre x)
while I 62 F  fg do
if I = (q; x1x
0
), x1 2  [ fg, x1x
0 6= , then I := ((q; x1); x0
)
else Ouput NO

od
Output YES
Notese que hemos introducido deliberadamente un pseudo{codigo que no necesariamente termina en todos los inputs. Esto es por analogacon las maquinas de
Turing y el estudio de los lenguajes recursivamente enumerables y recursivos. Aqu,
el pseudo{codigo tiene una interpretacion directa y natural en el caso determinstico
y genera una forma imprecisa en el caso indeterminstico. Esta interpretacion como
programa (determinstico) de este pseudo{codigo depende esencialmente de la ausencia de dos obstrucciones:
 La...