Maquina turing reconoce lenguaje cadenas con mismo número de ceros que de unos

[Leriu]

Diseñe una máquina de Turing para el siguiente lenguaje:

El conjunto de cadenas con el mismo número de ceros que de unos.

[javi in the sky]

Hola en este hilo creo que puedes encontrar la respuesta https://www.aprenderaprogramar.com/foros/index.php?topic=638.40

Saludos!

[Leriu]

Si, ya he revisado uno por uno pero aun no encuentro como resolver, me hes dificil entender este tipo de problemas, si pudieran ayudarme gracias.

[nosferacento]

Hola! Un posible algoritmo para resolver este problema es el siguiente:

Para cada símbolo 0 ó 1, se lee de la cadena de entrada colocada en la cinta, y se busca si existe otro 0 ó 1 en correspondencia. Si es así, se reemplazan ambos símbolos con otro símbolo de modo que los símbolos para los que ya se ha encontrado correspondencia se ignorarán en los siguientes pasos.

Si en la búsqueda no se encuentra correspondencia (se llega al final de la cadena sin encontrar el mismo símbolo, esto significa que no hay igual número de ceros que de unos) entonces se rechaza la cadena (no se acepta).

Si todos los 0s y 1s acaban en correspondencia la cadena se acepta.


La máquina sería esta (donde q es el estado inicial, R el estado de rechazo o no aceptación y F el estado de aceptación):

Ejemplos

Entrada: 001

Operación de la máquina:

q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1 ⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x ⊢ ΔxE0x ⊢ ΔxxCx ⊢ ΔxxxCΔ ⊢ R (reject)


Entrada: 0101

Operación de la máquina:

q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101 ⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01 ⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1 ⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx ⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx ⊢ ΔxxExx ⊢ ΔxxxEx ⊢ ΔxxxxEΔ ⊢ F (accept)

[Leriu]

 
Muchisimas gracias, gracias a esto estoy por entender mejor la maquina de turing, ahora me queda mas claro lo que tengo que hacer en mis siguientes problemas, de verdad te agradesco!!