Máquina de Turing Letras de Google

Hola.

Aquí presento la máquina de Turing que acepta las letras que forman la palabra GOOGLE es decir G,O,L,E

Q={q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10}

Σ ={0, 1}

Γ= {0, 1}

F={q8, q10}

Símbolo
estado	0	1
q0	(q1,1,R)	-
q1	-	(q2,1,R)
q2	(q3,0,R)	-
q3	(q4,0,R)	-
q4	(q5,0,R)	(q5,1,R)
q5	-	(q6,1,R)
q6	(q9,0,R)	(q7,1,R)
q7	-	(q8,1,R)
q9	(q10,0,R)	(q8,1,R)

Su grafo quedaría de la siguiente manera.

Máquina Turing G binario

Para el caso de la G que tiene código binario  01000111 de la letra G en ASCII es

Q={q0,q1,q2,q3,q4,q5,q6,q7,q8}

Σ ={0,1}

Γ= {0,1}

Tabla de transición es

Símbolo
estado	0	1
q0	(q1,1,R)	-
q1	-	(q2,1,R)
q2	(q3,0,R)	-
q3	(q4,0,R)	-
q4	(q5,0,R)	-
q5	-	(q6,1,R)
q6	-	(q7,1,R)
q7	-	(q8,1,R)
q8	Estado Final de aceptación

Por lo que solo acepta la cadena 01000111. Su gráfica en jflap queda de la siguiente forma.

Fe de erratas. En el post anterior los símbolos no salieron publicados correctamente.

Q es el conjunto finito de estados

Σ es el alfabeto de la cadena de entrada

Γ es el alfabeto de la cinta
q0 ∈ Q es el estado inicial
b es el espacio en blanco b  ∈  Γ   , pero b ∉ Σ
F ⊂ Q es el conjunto de estados finales

f: Q × Γ → Q × Γ × {I, D}

Doodle Maquina de Turing

En la década de los 30, el inglés Allan Turing diseñó  el modelo matemático de una máquina teórica  con un gran poder computacional, llamada máquina de Turing (M.T.)

Formalmente una máquina de Turing se define como:

MT= {Q, Σ, Γ, f, q0, b, F}

Q es el conjunto finito de estados

Σ es el alfabeto de la cadena de entrada

Γ es el alfabeto de la cinta
q0 ∈ Q es el estado inicial
b es el espacio en blanco b ∈ Γ, pero b no pertenece a Σ


F ⊂ Q es el conjunto de estados finales

f: Q × Γ→Q × Γ× {I, D}

Para el caso de la G que tiene código binario 01011 en el dodle de Google es

Q={q0,q1,q2,q3,q4,q5}

Σ = {0,1}

Γ= {0,1}

Tabla de transición para la entrada 00010 es la siguiente:

           

	símbolo
estado	0	1
q0	(q1,0,I)	-
q1	(q2,1,R)	-
q2	(q3,0,R)	-
q3	-	(q4,1,R)
q4	(q5,1,R)	-
q5	Estado final de aceptación

Su salida en el doodle es:

A continuación presento el diagrama de estados hecho en jflap

Fuente: 

García, L., Martínez, G. (2005). Máquinas de Turing. En Apuntes de teoría de autómatas y lenguajes formales. (pp. 109-126). Barcelona: Edit. Reverté.

Gramática libre de contexto, ejemplo lenguaje c

Una gramática libre de contexto es un conjunto finito de variables, cada una de las cuales representa un lenguaje.

De la forma V → W

Donde  V es un símbolo  no Terminal y W es una cadena de terminales y/o no terminales.

Tiene como origen la descripción de lenguajes naturales tal como se expresa en las siguientes reglas.

à

 –>

–>

–> niño

–> pequeño

Dónde:

Variables: ,, ,,.

Terminales: niño, pequeño.

Notación: Como ocurre en toda gramática formal que se ha estado estudiado en el curso se define mediante una cuádrupla de la siguiente manera.

G = (V, T, P, S)

V=El alfabeto de variables.

T=El alfabeto de símbolos terminales.

P=El conjunto de reglas de producción.

S=El símbolo inicial.

Las gramaticas libres de contexto pueden describir a gran parte de los lenguajes de programación, en el caso del lenguaje C, pongo el siguiente ejemplo que es la declaración de variables.

Las variables enteras en C se declaran de la siguiente manera.

chart a = 4 ;

lo que se puede traducir como

→=;

→chart

→ id

→ |n

→id

0,1,2,3,4,5....9

G= (,{chart,=,;,n},P,})

C maneja entre otros los siguientes tipos básicos de datos

chart, short, int, enum, long, float, double

por lo que la gramatica se puede definir de la siguiente manera

→;

→int

→chart

→short

→enum

→float

→double

→id

o utilizando |

→;

→int|chart|short|enum|float|double

→ id

→ |n

→id

n → 0,1,2,3,4,5....9

El árbol de derivación para

chart a = 4 ;

sería el siguiente

                           

Nueva versión del arbol

El siguiente sería el atómata de pila para chart id = 44;

Fuente: http://blog.gsystem.org/gramatica-de-libre-contexto/

         

Autómata Finito de Ascensor

Tabla de Estado

q	σ	δ(q, σ)
0	0	0
0	1	1
0	2	2
1	0	0
1	1	1
1	2	2
2	0	0
2	1	1
2	2	2

Otra versión del autómata sin incluir autoreferencias

Saga Vatídico - Robin Hobb

Bien, pues finalmente he terminado la saga de los Vatídicos de Robin Hobb, esta saga cuenta la vida de Traspie Hidalgo Vatídico y su familia monarca.
Los 2 primeros libros o cuatro si se leen de la edición anterior dividida en 6 libros, me han parecido muy buenos, en alguna ocasión lentos pero la narrativa no deja de impresionar, te transmite cada pensamiento de Traspie, tanto así que es difícil no tomarle cariño al personaje.

En cambio el último pareciese escrito por otro autor, la historia se vuelve precipitada, y el final forzado, (muy aparte de que no me gustado el final) . Pero si sumamos todos los libros resulta que el balance es positivo. Hobb Robin ha sabido plasmar un mundo donde la magia esta presente en dosis suficientes para que el lector sea cautivado. Su prosa es sencilla y se lee rápidamente. Por lo que si se es fanático de la fantasía es una lectura muy recomendable.

Samsung S5570L a Gingerbread de telcel funcionando

El día de hoy me he animado a hacer el cambio de mi Samsumg Galaxy mini Froyo a Gingerbread a pesar que Telcel aún no liberado la actualización y con los miedos que se presentan si el celular pudiera quedar inservible.

La actualización a quedado bien, pero no sé porque me da la impresión de que la red 2G (no utilizo 3G)   de Telcel en México pierde un poco de conexión, pero en lo demás no ha ocurrido nada, a excepción de un pequeño mensaje que me envió al principio de un error con lector con la síntesis de voz, que realmente no utilizó es más no sabía que el aparato lo tuviese. Revisándolo no se puede activar.

Sí aún así estás dispuesto a arriesgarte como yo puedes seguir las instrucciones en el foro .ignetwork.net o en androide peruano para complementar


http://foro.ignetwork.net/showthread.php?65204-Samsung-Galaxy-Mini-Gingerbread-2.3.4-Oficial-LatinoAmerica
http://androideperuano.blogspot.com/2011/08/galaxy-mini-firmware-gingerbread-para.html?m=0