Yo C

MaquinaTuring.c

Un Ejemplo Particular De La Máquina De Turing:

// Un Ejemplo Particular De La Máquina De Turing:
// Contar Los 1s En Una Cadena Así 10010110
// El Programa Lo Convierte A $10010110$
// Gilberto Stankiewicz
// http://www.stan.com.mx
// ESCOM, 4CM4
// Febrero 2008
// GCC

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char quintuples[][5] = {
	{'0','$','$','R','1'},
	{'1','$','$','R','6'},
	{'1','0','0','R','1'},
	{'1','1','a','L','2'},
	{'2','$','$','L','3'},
	{'2','0','0','L','2'},
	{'2','1','1','L','2'},
	{'3','0','1','R','4'},
	{'3','1','2','R','4'},
	{'3','2','3','R','4'},
	{'3','3','4','R','4'},
	{'3','4','5','R','4'},
	{'3','5','6','R','4'},
	{'3','6','7','R','4'},
	{'3','7','8','R','4'},
	{'3','8','9','R','4'},
	{'3','9','0','L','3'},
	{'3',' ','1','R','4'},
	{'4','$','$','R','5'},
	{'4','0','0','R','4'},
	{'5','0','0','R','5'},
	{'5','1','1','R','5'},
	{'5','a','1','R','1'}
	};
	
int pasos = 23;
char estado = 0, posicion;

// validar que sean 1s y 0s
int validar (char* cadena) {
	int i, tamano;
	
	tamano = strlen(cadena);
	
	for (i = 0; i < tamano; i++) {
		if (cadena[i] != '0' && cadena[i] != '1') {
			fprintf(stderr, "La cadena %s no cumple con el formato.\n", cadena);
			return -1;
		}
	}
	return 0;
}

void resolver (char* cadena)  {
	char* cinta;
	int i, j;

	// armar la cinta
	int espacios = strlen(cadena) / 10 + 1;
	int tamano = strlen(cadena) + espacios + 2;
	
	printf("tamano cinta: %d \n", tamano);
	
	cinta = (char*) malloc(tamano * sizeof(char));
	strcpy(cinta, "");
	for (i = 0; i < espacios; i++)
		strcat(cinta, " ");
	strcat(cinta, "$");
	strcat(cinta, cadena);
	strcat(cinta, "$");
	
	printf("cinta: %s \n", cinta);
	
	// seguir algoritmo
	estado = '0';
	posicion = espacios;
	
	while (1) {
		// imprimir cinta
		printf("%s\n", cinta);
		
		// línea estado
		for (j = 0; j < posicion; j++) {
			printf(" ");
		}
		printf("^ %c\n", estado);
		
		for (i = 0; i < pasos; i++) {
			if (estado == quintuples[i][0] && cinta[posicion] == quintuples[i][1]) {
				cinta[posicion] = quintuples[i][2];
				estado = quintuples[i][4];
				if (quintuples[i][3] == 'R')
					posicion++;
				else
					posicion--;
				break;
			}
		}
		if (i == pasos) 
			break;
	}
}

int main(int argc, char *argv[]) {
	int i, j, tamano; 

	// modo de empleo
	if (argc == 1) {
		fprintf(stderr, "Error: falta operando.\n");
		fprintf(stderr, "Modo de empleo: %s CADENA ...\n", argv[0]);
		fprintf(stderr, "Cuenta los unos en una CADENA de ceros y unos. Simulando la maquina de turing.\n");
		fprintf(stderr, "Ejemplo: %s 0011010011 1001\n", argv[0]);
		exit(-1);
	}
	
	// por cada CADENA simular el algoritmo
	for (i = 1; i < argc; i++) {
		if(validar(argv[i]) != -1)
			resolver(argv[i]);
		printf("\n");
	}
}

Otros Temas

ASM
C
C++
C#
Java
PL/SQL
PHP
Python
VB