Lenguaje Y automatas

examen 1 examen 2

L = { 0 n 1 n   : n > 0 } Lo primero que haremos es limitar el alfabeto a Σ = { 0 , 1 } Σ = { 0 , 1 } así nos aseguramos de que sólo puede aceptar palabras con de entrada con símbolos 1 y 0. Los símbolos de cinta serán T = { 0 , 1 , B , X , Y } = { 0 , 1 , B , X , Y } siendo  B  el símbolo en blanco. La MT consta de cinco estados: q 0 , q 1 , q 2 , q 3 , q 4 q 0 , q 1 , q 2 , q 3 , q 4 Los estados  q 0  y  q 4  son el inicial y el final, respectivamente. Inicialmente, la cabeza señala el primer 0. Lo cambia por  X  y se desplaza a la derecha en busca del primer 1 para cambiarlo por  Y : δ ( q 0 , 0 ) = ( q 1 , X , R ) δ ( q 0 , 0 ) = ( q 1 , X , R ) δ ( q 1 , 0 ) = ( q 1 , 0 , R ) δ ( q 1 , 0 ) = ( q 1 , 0 , R ) Es decir, mientras haya 0's, se mantiene en el estado  q 1  . δ ( q 1 , 1 ) = ( q 2 , Y , L ) δ ( q 1 , 1 ) = ( q 2 , Y , L ) Ha encontrado el primer 1. Lo cambia por  Y  y pasa al estado...