Técnicas usadas para la construcción de autómatas

EJEMPLOS APLICATIVOS DE MAQUINA TURING
MT para aceptar L={011n/n 1} Inicialmente la cinta contiene 011n seguido de un número infinito deblancos.
1. M lee el # mas significativo y lo reemplaza por una x.
2. S mueve hasta el 1 mas significativo y lo reemplaza por y.
3. El ciclo serepite:
a. Si al buscar un 1, m encuentra #
b. Si al buscar un 0 ya no hay, m busca si ha 1
Q = {q0, q1, q2, q3, q4}, = {0,1}, = {0,1,x,y,#},F={q4} q0
q1 = substitución de 0 por y
q2 =búsqueda de 1, substitución por y
q3 =búsqueda de 0
q4 =búsqueda de 1 para ver si se acepta.PROCESO DE RECONOCIMIENTO DE CADENAS

Se parte del estado inicial, y la cinta contiene símbolos de entrada.
Se efectúan las transicionespertinentes según la función de transición.
Si la cabeza lectora rebasa el extremo izquierdo de la cinta, la cadena es rechazada y el proceso termina(terminación anormal).
Si la máquina alcanza el estado de parada, la cadena es aceptada.

CONSTRUCCION MODULAR DE UNA MAQUINA TURING

Ejemplo:25.3E-18

Definición: Forma sentencial
Sea G = una gramática
a) S es una forma sentencial
b) Si S es una forma sentencial y P, entoncesN es también una forma sentencial.
Una forma sentencial que no contiene no-terminales se llama sentencia generada por G.
Definición: Ellenguaje generado por una gramática G, denotado por L (G), es el conjunto de sentencias generadas por G.
Definición: Sea G=
+cierre transitivo